Réunion d'hiver SMC 2015
Université McGill, 4 - 7 décembre 2015
- BORIS BUKH, Carnegie Mellon University
Extremal problem for graph eigenvalue multiplicity [PDF]
-
Given $\lambda$ what is the maximal multiplicity of eigenvalue $\lambda$ in a graph on $n$ vertices? We give an asymptotic answer for the analogous problem for digraphs, and discuss the known results for graphs, and outline connections to several other problems in extremal combinatorics.
- ENDRE CSÓKA, MTA Alfréd Rényi Institute of Mathematics
Vizing’s Theorem for Graphings [PDF]
-
Vizing's Theorem states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence and measurable group theory. We prove that every graphing of maximum degree d admits a \emph{measurable} edge-coloring with $d+1$ colors, assuming a stronger version of Vizing's Theorem. Without this assumption, we can still prove the same with $n + O(\sqrt{n})$ colors, or with $d+1$ colors for bipartite graphs.
- ZDENEK DVORAK, Charles University in Prague
List-coloring embedded graphs without cycles of lengths 4 to 8 [PDF]
-
The well-known Steinberg's conjecture postulates that every planar graph without $4$-cycles and $5$-cycles is $3$-colorable. The list-coloring version of this claim is known to be false. However, we prove that excluding cycles of lengths $4$ to $8$ is sufficient to guarantee $3$-choosability of a planar graph, thus answering a question of Borodin. For the proof, we use a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring.
Joint work with Luke Postle.
- YUVAL FILMUS, Technion – Israel Institute of Technology
Triangle-intersecting families of graphs [PDF]
-
How many graphs can a collection of subgraphs of $K_n$ consist of, if the intersection of any two contains a triangle? Simonovits and Sós asked this question in 1976, in the context of Erdös–Ko–Rado theory. They conjectured that such a collection can contain at most 1/8 of the graphs. This bound is attained by a "triangle-junta", consisting of all supergraphs of a fixed triangle.
It is trivial to see that such a family contains at most 1/2 of the graphs. Chung, Frankl, Graham, and Shearer improved this bound to 1/4 in 1986, using Shearer's entropy lemma. This is where matters stood until Ellis, Friedgut, and myself proved the optimal upper bound 1/8 in 2010.
Our proof uses a spectral technique known variously as Hoffman's bound, the Lovász theta function, and Friedgut's method. The technique involves cooking up a matrix whose rows and columns are indexed by subgraphs of $K_n$, entries corresponding to non-triangle-intersecting pairs of subgraphs are 0, the maximal eigenvalue is 1, and the minimal eigenvalue is –1/7.
Our main tool is the cut distribution of a graph, which is the distribution of the number of edges cut by a random partition of the vertex set. We find a linear combination of cut probabilities whose value always ranges between 1 and –1/7, and use it to construct the matrix mentioned above.
- KRYSTAL GUO, University of Waterloo
Quantum walks and graph isomorphism [PDF]
-
A quantum walk is a quantum process on graph, whose transition matrix is a graph invariant. There are many proposals for classes of graphs where some property of the transition matrix is a complete graph invariant. In particular, it is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We will discuss linear algebraic and combinatorial properties of graphs which are distinguished by this invariant and also present strongly regular graphs on which this invariant fails.
- TONY HUYNH, Université libre de Bruxelles
The forbidden minors for isometric realizability in the plane [PDF]
-
We say that a graph $G$ is \textit{universally isometrically realizable} in $\ell_{\infty}^{k}$, if for every metric $d: E(G) \to \mathbb{R}_+$, there is a collection of points $(q_v)_{v \in V(G)}$ in $\mathbb{R}^k$ such that $\| q_v - q_w \|_\infty=d_{vw}$ for all $vw \in E(G)$. It is easy to show that for each fixed $k$, the property of being universally isometrically realizable in $\ell_{\infty}^{k}$ is minor-closed. We determine the complete set of excluded minors for $k = 2$. The two excluded minors are the wheel on $5$ vertices and the graph obtained by gluing two copies of $K_4$ along an edge and then deleting that edge.
This is joint work with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.
- ALEXANDR KOSTOCHKA, University of Illinois at Urbana-Champaign
Colorings and list colorings of sparse graphs [PDF]
-
The goal of the talk is to present two closely related results.
The first (joint with Reiniger) is a proof of a conjecture by Chen, Erd\H os, Gy\' arf\' as and Schelp on the number of edges in 4-critical graphs that become bipartite after deleting 3 edges.
A useful part of the proof is the result of Alon and Tarsi that every bipartite graph with maximum
average degree at most $4$ is 3-list-colorable. It would be helpful if every such bipartite graph
after adding one more edge were still 3-list-colorable. But this turned out to be not the case.
The second result (joint with Alon, Reiniger, West and Zhu) is a construction for every $k$ and $g$ of a bipartite graph of girth at least $g$ that after deleting any edge has maximum average degree at most $2(k-1)$ but is not $k$-list-colorable. As a biproduct, we get a new construction of graphs and hypergraphs with arbitrarily high girth and chromatic number.
- BERNARD LIDICKY, Iowa State University
Inducibility of Short Cycles [PDF]
-
In 1975, Pippinger and Golumbic conjectured that in graphs the maximum induced density of a k-cycle is $\frac{k!}{k^k - k}$ when $k \geq 5$.
The case of $k = 5$ was solved recently by Balogh, Hu, L., Pfender. We show that it is possible to extend the result to other small $k$. The results are obtained using Flag algebras and stability.
This is joint work with Pfender and Brandt.
- CHUN-HUNG LIU, Princeton University
Minimum degree and lengths of cycles [PDF]
-
We will address several minimum degree conditions for graphs forcing the existence of cycles of specific lengths.
First, we prove that every graph of minimum degree at least $k+1$ contains $\lfloor k/2 \rfloor$ cycles with consecutive even lengths. When $k$ is an even integer, it confirms one of Thomassen's conjecture which states that every graph of minimum degree at least $k+1$ contains a cycle of length $2m$ modulo $k$, for each integer $m$ with $0 \leq 2m < k$. Our result is tight and improves a theorem of Fan.
Second, we prove that every graph of minimum degree at least $k+4$ contains $k$ cycles whose lengths forming an arithmetic progression of common difference one or two. This implies that minimum degree $k+4$ suffices in the mentioned Thomassen's conjecture for odd $k$ and improves the best previous result of this conjecture which was proved by Diwan.
Third, we prove that the mentioned minimum degree condition can be further improved to be $k+3$ for 3-connected non-bipartite graphs. This improves another result of Fan and provides a better answer of a question of Bondy and Vince.
This work is joint with Jie Ma.
- PETER NELSON, University of Waterloo
Cycles in random subgraphs [PDF]
-
Let $\mu > 2$ and $\epsilon > 0$. I will discuss a result showing that, if $G$ is a sufficiently large simple graph of average degree at least $\mu$, and $H$ is a random spanning subgraph of $G$ formed by including each edge independently with probability $p \ge \tfrac{1}{\mu-1} + \epsilon$, then $H$ contains a cycle with probability at least $1 - \epsilon$.
- LUKE POSTLE, University of Waterloo
Improved Bounds on the Chromatic Number [PDF]
-
In 1998, Reed proved that the chromatic number of a graph is bounded away from its maximum degree and towards its clique number. We examine various generalizations of this result, specifically in regards to list coloring, local versions, and maximum average degree.
- MUSTAZEE RAHMAN, MIT
Local algorithms for independent sets in random graphs [PDF]
-
How large can an independent set be in a random d-regular graph? How large can it be if we are to construct it using a (possibly randomized) algorithm that is local in nature? We will discuss a notion of local algorithms for combinatorial optimization problems on large, random d-regular graphs. We will then briefly explain why, for asymptotically large d, local algorithms can only produce independent sets of size at most half of the largest ones. The factor of 1/2 turns out to be optimal. Joint work with B\'{a}lint Vir\'{a}g.
- LIANA YEPREMYAN, McGill University
The Local Stability Method and the Tur\'an numbers of extensions [PDF]
-
The \textit{Tur\'an number} of a graph $G$, denoted by $ex(n,G)$, is the maximum number of edges in an $G$-free graph on $n$ vertices. The \textit{Tur\'an density} of a graph $G$, denoted by $\pi(G)$, is the limit as $n$ tends to infinity of the maximum edge density of an $G$-free graph on $n$ vertices. Unless $\pi(G) =0$, it captures the asymptotic behaviour of $ex(n,G)$.
During this talk I will discuss a method, which we call \textit{local stability method}, that allows one to obtain exact Tur\'an numbers from Tur\'an density results. This method can be thought of as an extension of the classical stability method by generically utilizing Lagrangians and symmetrization. Using it, we solved a conjecture of Frankl and Füredi from 1980's and obtained the Tur\'an number of a hypergraph called, \textit{generalized triangle}, for uniformities 5 and 6. Further, our method is more generally applicable for determining Tur\'an numbers of so-called \textit{extensions}.
This is joint work with Sergey Norin.
