Seminars and Colloquia by Series

Counting critical subgraphs in k-critical graphs

Series
Graph Theory Seminar
Time
Thursday, October 3, 2019 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jie Ma – University of Science and Technology of China

A graph is $k$-critical if its chromatic number is $k$ but any its proper subgraph has chromatic number less than $k$. Let $k\geq 4$. Gallai asked in 1984 if any $k$-critical graph on $n$ vertices contains at least $n$ distinct $(k-1)$-critical subgraphs. Improving a result of Stiebitz, Abbott and Zhou proved in 1995 that every such graph contains $\Omega(n^{1/(k-1)})$ distinct $(k-1)$-critical subgraphs. Since then no progress had been made until very recently, Hare resolved the case $k=4$ by showing that any $4$-critical graph on $n$ vertices contains at least $(8n-29)/3$ odd cycles. We mainly focus on 4-critical graphs and develop some novel tools for counting cycles of specified parity. Our main result shows that any $4$-critical graph on $n$ vertices contains $\Omega(n^2)$ odd cycles, which is tight up to a constant factor by infinite many graphs. As a crucial step, we prove the same bound for 3-connected non-bipartite graphs, which may be of independent interest. Using the tools, we also give a very short proof to the Gallai's problem for the case $k=4$. Moreover, we improve the longstanding lower bound of Abbott and Zhou to $\Omega(n^{1/(k-2)})$ for the general case $k\geq 5$. Joint work with Tianchi Yang.

Quasirandom permutations

Series
Graph Theory Seminar
Time
Friday, September 13, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker
Dan Kral – Masaryk University and University of Warwick

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. For example, it is well-known that a graph G with edge-density p is quasirandom if and only if the density of C_4 in G is p^4+o(p^4); this property is known to equivalent to several other properties that hold for truly random graphs.  A similar phenomenon was established for permutations: a permutation is quasirandom if and only if the density of every 4-point pattern (subpermutation) is 1/4!+o(1).  We strengthen this result by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-point patterns is 1/3+o(1). More generally, we classify all sets of 4-point patterns having such property.

The talk is based on joint work with Timothy F. N. Chan, Jonathan A. Noel, Yanitsa Pehova, Maryam Sharifzadeh and Jan Volec.

Independent set permutations, and matching permutations

Series
Graph Theory Seminar
Time
Thursday, April 18, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
David Galvin – University of Notre Dam
To any finite real sequence, we can associate a permutation $\pi$, via: $\pi(k)$ is the index of the $k$th smallest element of the sequence. This association was introduced in a 1987 paper of Alavi, Malde, Schwenk and Erd\H{o}s, where they used it to study the possible patterns of rises and falls that can occur in the matching sequence of a graph (the sequence whose $k$th term is the number of matchings of size $k$), and in the independent set sequence. The main result of their paper was that {\em every} permutation can arise as the ``independent set permutation'' of some graph. They left open the following extremal question: for each $n$, what is the smallest order $m$ such that every permutation of $[n]$ can be realized as the independent set permutation of some graph of order at most $m$? We answer this question. We also improve Alavi et al.'s upper bound on the number of permutations that can be realized as the matching permutation of some graph. There are still many open questions in this area. This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame.

Fractional coloring with local demands

Series
Graph Theory Seminar
Time
Thursday, April 11, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tom Kelly – University of Waterloo

In a fractional coloring, vertices of a graph are assigned subsets of the [0, 1]-interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most k if it admits a fractional coloring in which the amount of "color" assigned to each vertex is at least 1/k. We investigate fractional colorings where vertices "demand" different amounts of color, determined by local parameters such as the degree of a vertex. Many well-known results concerning the fractional chromatic number and independence number have natural generalizations in this new paradigm. We discuss several such results as well as open problems. In particular, we will sketch a proof of a "local demands" version of Brooks' Theorem that considerably generalizes the Caro-Wei Theorem and implies new bounds on the independence number. Joint work with Luke Postle.

On the number of cliques in graphs with a forbidden clique minor

Series
Graph Theory Seminar
Time
Thursday, March 28, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Fan Wei – Stanford University
Reed and Wood and independently Norine, Seymour, Thomas, and Wollan showed that for each $t$ there is $c(t)$ such that every graph on $n$ vertices with no $K_t$ minor has at most $c(t)n$ cliques. Wood asked in 2007 if $c(t)

The upper tail for triangles in sparse random graphs

Series
Graph Theory Seminar
Time
Thursday, November 1, 2018 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Wojtek Samotij – Tel Aviv University
Let X denote the number of triangles in the random graph G(n, p). The problem of determining the asymptotics of the rate of the upper tail of X, that is, the function f_c(n,p) = log Pr(X > (1+c)E[X]), has attracted considerable attention of both the combinatorics and the probability communities. We shall present a proof of the fact that whenever log(n)/n << p << 1, then f_c(n,p) = (r(c)+o(1)) n^2 p^2 log(p) for an explicit function r(c). This is joint work with Matan Harel and Frank Mousset.

Matroids over pastures

Series
Graph Theory Seminar
Time
Thursday, October 25, 2018 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matthew Baker – Math, GT
We present an algebraic framework which simultaneously generalizes the notion of linear subspaces, matroids, valuated matroids, oriented matroids, and regular matroids. To do this, we first introduce algebraic objects which we call pastures; they generalize both hyperfields in the sense of Krasner and partial fields in the sense of Semple and Whittle. We then define matroids over pastures; in fact, there are at least two natural notions of matroid in this general context, which we call weak and strong matroids. We present ``cryptomorphic'’ descriptions of each kind of matroid. To a (classical) rank-$r$ matroid $M$ on $E$, we can associate a universal pasture (resp. weak universal pasture) $k_M$ (resp. $k_M^w$). We show that morphisms from the universal pasture (resp. weak universal pasture) of $M$ to a pasture $F$ are canonically in bijection with strong (resp. weak) representations of $M$ over $F$. Similarly, the sub-pasture $k_M^f$ of $k_M^w$ generated by ``cross-ratios'', which we call the foundation of $M$, parametrizes rescaling classes of weak $F$-matroid structures on $M$. As a sample application of these considerations, we give a new proof of the fact that a matroid is regular if and only if it is both binary and orientable.

Limitations of Sums of Squares Method for Turan Problems

Series
Graph Theory Seminar
Time
Thursday, October 11, 2018 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Greg Blekherman – Georgia Tech
A sum of squares of real numbers is always nonnegative. This elementary observation is quite powerful, and can be used to prove graph density inequalities in extremal combinatorics, which address so-called Turan problems. This is the essence of semidefinite method of Lov\'{a}sz and Szegedy, and also Cauchy-Schwartz calculus of Razborov. Here multiplication and addition take place in the gluing algebra of partially labelled graphs. This method has been successfully used on many occasions and has also been extensively studied theoretically. There are two competing viewpoints on the power of the sums of squares method. Netzer and Thom refined a Positivstellensatz of Lovasz and Szegedy by showing that if f> 0 is a valid graph density inequality, then for any a>0 the inequality f+a > 0 can be proved via sums of squares. On the other hand, Hatami and Norine showed that testing whether a graph density inequality f > 0 is valid is an undecidable problem, and also provided explicit but complicated examples of inequalities that cannot be proved using sums of squares. I will introduce the sums of squares method, do several examples of sums of squares proofs, and then present simple explicit inequalities that show strong limitations of the sums of squares method. This is joint work in progress with Annie Raymond, Mohit Singh and Rekha Thomas.

The Grid Theorem for Vertex Minors

Series
Graph Theory Seminar
Time
Thursday, August 30, 2018 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCarty – University of Waterloo
Vertex minors are a weakening of the notion of induced subgraphs that benefit from many additional nice properties. In particular, there is a vertex minor version of Menger's Theorem proven by Oum. This theorem gives rise to a natural analog of branch-width called rank-width. Similarly to the Grid Theorem of Robertson and Seymour, we prove that a class of graphs has unbounded rank-width if and only if it contains all "comparability grids'' as vertex minors. This is joint work with Jim Geelen, O-joung Kwon, and Paul Wollan.

The Generalized Györi-Lovasz Theorem

Series
Graph Theory Seminar
Time
Thursday, April 19, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alexander Hoyer – Math, GT
Györi and Lovasz independently proved that a k-connected graph can be partitioned into k subgraphs, with each subgraph connected, containing a prescribed vertex, and with a prescribed vertex count. Lovasz used topological methods, while Györi found a purely graph theoretical approach. Chen et al. later generalized the topological proof to graphs with weighted vertices, where the subgraphs have prescribed weight sum rather than vertex count. The weighted result was recently proven using Györi's approach by Chandran et al. We will use the Györi approach to generalize the weighted result slightly further. Joint work with Robin Thomas.

Pages