Publications related to A bipartite strengthening of the Crossing Lemma

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.

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Graph Heat Mixture Model Learning

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph inference methods have recently attracted a great interest from the scientific community, due to the large value they bring in data interpretation and analysis. However, most of the available state-of-the-art methods focus on scenarios where all avai ...

IEEE2018

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

Conditional expanding bounds for two-variable functions over finite valuation rings

Van Thang Pham

In this paper, we use methods from spectral graph theory to obtain some results on the sum-product problem over finite valuation rings R of order q(r) which generalize recent results given by Hegyvari and Hennecart (2013). More precisely, we prove that, fo ...

Academic Press Ltd- Elsevier Science Ltd2017

On the Difficulty of Selecting Ising Models with Approximate Recovery

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

Pierre Vandergheynst, Xavier Bresson, Rodrigo Cerqueira Gonzalez Pena

We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion ker- nel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot ...

Ieee2016

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

A bipartite strengthening of the Crossing Lemma

Graph Chatbot

Chat with Graph Search

Incidences Between Planes Over Finite Fields

Ramsey-Turan numbers for semi-algebraic graphs

Graph Heat Mixture Model Learning

Note on k-planar crossing numbers

Extension complexity of stable set polytopes of bipartite graphs

Geometric Graph Matching Using Monte Carlo Tree Search

Conditional expanding bounds for two-variable functions over finite valuation rings

On the Difficulty of Selecting Ising Models with Approximate Recovery

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

The Erdos-Hajnal conjecture for rainbow triangles

Incidences Between Planes Over Finite Fields

Conditional expanding bounds for two-variable functions over finite valuation rings

Ramsey-Turan numbers for semi-algebraic graphs

Graph Heat Mixture Model Learning

Note on k-planar crossing numbers

Extension complexity of stable set polytopes of bipartite graphs

On the Difficulty of Selecting Ising Models with Approximate Recovery

The Erdos-Hajnal conjecture for rainbow triangles

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

Geometric Graph Matching Using Monte Carlo Tree Search