Seminar Calendar
for Graph Theory and Combinatorics events the next 12 months of Sunday, January 1, 2017.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    December 2016           January 2017          February 2017    
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
              1  2  3    1  2  3  4  5  6  7             1  2  3  4
  4  5  6  7  8  9 10    8  9 10 11 12 13 14    5  6  7  8  9 10 11
 11 12 13 14 15 16 17   15 16 17 18 19 20 21   12 13 14 15 16 17 18
 18 19 20 21 22 23 24   22 23 24 25 26 27 28   19 20 21 22 23 24 25
 25 26 27 28 29 30 31   29 30 31               26 27 28            
                                                                   

Tuesday, January 24, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 24, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Many $T$ copies in $H$-free subgraphs of random graphs
Abstract: For two fixed graphs $T$ and $H$ let $ex(G(n,p),T,H)$ be the random variable counting the maximum number of copies of $T$ in an $H$-free subgraph of the random graph $G(n,p)$. We show that for the case $T=K_m$ and $\chi(H)>m$ the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and $m_2(H)=\max_{H'\subset H, |V(H')|\geq 3}\left\{ \frac{e(H')-1}{v(H')-2} \right\}$. When $m_2(H)>m_2(K_m)$ we prove that with high probability, depending on the value of $p$, either one can keep almost all copies of $K_m$ in an $H$-free subgraph of $G(n,p)$, or it is asymptotically best to take a $\chi(H)-1$ partite subgraph of $G(n,p)$. The transition between these two behaviors occurs at $p=n^{-1/m_2(H)}$. When $m_2(H)< m_2(K_m)$, the above cases still exist, however for $\delta>0$ small at $p=n^{-1/m_2(H)+\delta}$ one can typically still keep most of the copies of $K_m$. The reason for this is that although $K_m$ has the minimum average degree among the $m$-color-critical graphs, it does not have the smallest $m_2(G)$ among such graphs. This is joint work with N. Alon and C. Shikhelman.

Tuesday, January 31, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 31, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Anton Bernshteyn (Illinois Math)
DP-colorings of graphs with high chromatic number
Abstract: Let $G$ be an $n$-vertex graph with chromatic number $\chi(G)$. Ohba's conjecture (now a celebrated theorem due to Noel, Reed, and Wu) claims that whenever $\chi(G) \geq (n-1)/2$, the list chromatic number of $G$ equals $\chi(G)$. DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle. We establish an analog of Ohba's conjecture for the DP-chromatic number; namely we show that the DP-chromatic number of $G$ also equals $\chi(G)$ as long as $\chi(G)$ is ``sufficiently large''. In contrast to the list coloring case, ``large'' here means $\chi(G)\geq n-O(\sqrt{n})$, and we also show that this lower bound is best possible (up to the constant factor in front of $\sqrt{n}$). This is joint work with Alexandr Kostochka and Xuding Zhu.

Tuesday, February 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 7, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Ruth Luo (Illinois Math)
The maximum number of cliques in graphs without long cycles
Abstract: The Erdős-Gallai Theorem states that for $k\geq 3$ every graph on $n$ vertices with more than $\frac{1}{2}(k-1)(n-1)$ edges contains a cycle of length at least $k$. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples $H_{n,k,t}$ and $H_{n,k,2}$. In this talk, we generalize the result of Kopylov to bound the number of $s$-cliques in a graph with circumference less than $k$. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of $s$-cliques in a graph with no path on $k$-vertices.

Tuesday, February 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 14, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Sarka Petrickova (Illinois Math)
Families in posets minimizing the number of comparable pairs
Abstract: Given a poset $P$, we say a family $\mathcal{F} \subseteq P$ is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the centeredness property if for any $M$, amongst all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ (where $(A_1,\dots,A_n)\le (B_1,\dots,B_n)$ if $A_i\le B_i$ for each $i\in [n]$) also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbf{F}_q^n$ has the centeredness property. This is joint work with Jozsef Balogh and Adam Zsolt Wagner.

Tuesday, February 21, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 21, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Douglas B. West (Illinois Math and Zhejiang Normal University)
Reconstruction from the deck of $k$-vertex induced subgraphs
Abstract: The $k$-deck of a graph is its multiset of subgraphs induced by $k$ vertices; we ask whether the $k$-deck determines the graph. We show that a complete $r$-partite graph is determined by its $(r+1)$-deck. Letting $n=|V(G)|$, we generalize a result of Bollobás by showing that for $l=(1-o(1))n/2$, almost every graph $G$ is determined by various sets of ${l+2\choose 2}$ subgraphs with $n-l$ vertices. However, when $l=n/2$, the entire $(n-l)$-deck does not always determine whether $G$ is connected (it fails for $n$-vertex paths). We strengthen a result of Manvel by proving for each $l$ that when $n$ is sufficiently large (at least $l^{l^2}$), the $(n-l)$-deck determines whether $G$ is connected ($n\ge25$ suffices when $l=3$, and $n\le 2l$ cannot suffice). Finally, for every graph $G$ with maximum degree $2$, we determine the least $k$ such that $G$ is reconstructible from its $k$-deck, which involves extending a result of Stanley. This is joint work with Hannah Spinoza.

Tuesday, February 28, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 28, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Misha Lavrov (Carnegie Mellon University)
Distance-uniform graphs with large diameter
Abstract: We say that a graph is epsilon-distance-uniform if there is a value d (called the critical distance) such that, for every vertex v, all but an epsilon fraction of the other vertices are at distance exactly d from v. Random graphs are distance-uniform with logarithmic critical distance, and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that the critical distance (equivalently, the diameter) of a distance-uniform graph must always be logarithmic. In this talk, we use a generalization of the Towers of Hanoi puzzle to construct distance-uniform graphs with a much larger diameter: for constant epsilon, as large as n^O(1/log log n). We show that this construction is more or less worst possible for sufficiently small epsilon, leaving open the possibility that for large epsilon, much worse cases exist. This is joint work with Po-Shen Loh.

Tuesday, March 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 7, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Gexin Yu (College of William & Mary)
The strong chromatic index of graphs with maximum degree four is at most 21
Abstract: A strong edge-coloring of a graph $G$ is a coloring of the edges such that every color class induces a matching in $G$. The strong chromatic index of a graph is the minimum number of colors needed in a strong edge-coloring of the graph. In 1985, Erdős and Nešetřil conjectured that every graph with maximum degree $\Delta$ has a strong edge-coloring using at most $\frac{5}{4}\Delta^2$ colors if $\Delta$ is even, and at most $\frac{5}{4}\Delta^2 - \frac{1}{2}\Delta + \frac{1}{4}$ if $\Delta$ is odd. This conjecture is widely unresolved with the only verified case being for $\Delta = 3$, due independently to Andersen as well as Horák, Qing, and Trotter. In this paper, we show that the strong chromatic index of graphs (where we allow for multiple edges) with maximum degree at most four is always at most 21. This improves a previous bound due to Cranston and moves closer to the conjectured upper bound of 20. This is joint work with Mingfang Huang and Michael Santana.

Tuesday, March 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 14, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Katherine Anders (The University of Texas at Tyler)
Rooted forests that avoid sets of permutations
Abstract: An unordered rooted labeled forest avoids the pattern $\pi\in\mathcal{S}_n$ if the sequence obtained from the labels along the path from the root to any vertex does not contain a subsequence that is in the same relative order as $\pi$. We enumerate several classes of forests that avoid certain sets of permutations, including the set of unimodal forests, via bijections with set partitions with certain properties. This is joint work with Kassie Archer.

Tuesday, March 28, 2017

Graph Theory and Combinatorics Semianr
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 28, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Zoltán Furëdi (Illinois Math and Renyi Institute of Mathematics)
Combinatorial geometry problems and Turán hypergraphs
Abstract: We overlook a few applications of using extremal hypergraphs in combinatorial geometry questions. A sample result: Let $h(n)$ be the maximum number of triangles among $n$ points on the plane which are almost regular (all three angles are between 59 to 61 degrees). Conway, Croft, Erdős and Guy (1979) proved an upper bound for $h(n)$ and conjectured that $h(n)=(1+o(1)) n^3/ 24$. We prove this (and other) conjectures. Among our main tools we use Razborov's flag algebra method to determine the Turán numbers of certain 3-uniform hypergraphs. This is a joint work with Imre Bárány (with some computer help from Manfred Scheucher).