Publication

Degenerate crossing numbers

Related publications (157)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Classifying Dyads for Militarized Conflict Analysis

Robert West

Understanding the origins of militarized conflict is a complex, yet important undertaking. Existing research seeks to build this understanding by considering bi-lateral relationships between entity pairs (dyadic causes) and multi-lateral relationships amon ...

ASSOC COMPUTATIONAL LINGUISTICS-ACL2021

Demography of galactic technosignatures

Claudio Grimaldi

Probabilistic arguments about the existence of technological life beyond Earth traditionally refer to the Drake equation to draw possible estimates of the number of technologically advanced civilizations releasing, either intentionally or not, electromagne ...

OXFORD UNIV PRESS2021

Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity

Nicolas Henri Bernard Flammarion, Scott William Pesme, Loucas Pillaud-Vivien

Understanding the implicit bias of training algorithms is of crucial importance in order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through i ...

2021

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...

SPRINGER2020

Edge colorings of graphs without monochromatic stars

Abhishek Methuku

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...

ELSEVIER2020

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

Graph Signal Processing: Foundations and Emerging Directions [From the Guest Editors]

Dimitri Nestor Alice Van De Ville, Negar Kiyavash

The articles in this special section focus on graph signal processing. Generically, the networks that sustain our societies can be understood as complex systems formed by multiple nodes, where global network behavior arises from local interactions between ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Flooding And Diameter In General Weighted Random Graphs

Thomas Mountford, Jacques Saliba

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, ...

CAMBRIDGE UNIV PRESS2020

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Dimitri Nestor Alice Van De Ville, Thomas William Arthur Bolton, Raphaël Pierre Liégeois

The emerging field of graph signal processing (GSP) allows one to transpose classical signal processing operations (e.g., filtering) to signals on graphs. The GSP framework is generally built upon the graph Laplacian, which plays a crucial role in studying ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Graph-based regularization of inverse problems in imaging

Mattia Rossi

As of today, the extension of the human visual capabilities to machines remains both a cornerstone and an open challenge in the attempt to develop intelligent systems. On the one hand, the development of more and more sophisticated imaging devices, capable ...

EPFL2020