- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

(Alon-Tarsi Conjecture): For even n, the number of even nxn Latin squares

differs from the number of odd nxn Latin squares.

(Stones-Wanless, Kotlar Conjecture): For all n, the number of even nxn

Latin squares with the identity permutation as first row and first column

differs from the number of odd nxn Latin squares of this type.

(Aharoni-Berger Conjecture): Let M and N be two matroids on the same

vertex set, and let A1,...,An be sets

of size n + 1 belonging to both M and N. Then there exists a set belonging

to both M and N and meeting all Ai.

differs from the number of odd nxn Latin squares.

(Stones-Wanless, Kotlar Conjecture): For all n, the number of even nxn

Latin squares with the identity permutation as first row and first column

differs from the number of odd nxn Latin squares of this type.

(Aharoni-Berger Conjecture): Let M and N be two matroids on the same

vertex set, and let A1,...,An be sets

of size n + 1 belonging to both M and N. Then there exists a set belonging

to both M and N and meeting all Ai.

We prove equivalence of the first two conjectures and a special case

of the third one and use these results to show that Alon-Tarsi Conjecture

implies Rota's bases conjecture for odd n and

any system of n non-singular real valued matrices where one of them is

non-negative and the remaining have non-negative inverses.Joint work with Ron Aharoni.

Series: Graph Theory Seminar

In this talk, we discuss our recent progress on the famous directed cycle

double cover conjecture of Jaeger. This conjecture asserts that every

2-connected graph admits a collection of cycles such that each edge is in

exactly two cycles of the collection. In addition, it must be possible to

prescribe an orientation to each cycle so that each edge is traversed in

both ways.

We plan to define the class of weakly robust trigraphs and prove that a

connectivity augmentation conjecture for this class implies general

directed cycle double cover conjecture.

double cover conjecture of Jaeger. This conjecture asserts that every

2-connected graph admits a collection of cycles such that each edge is in

exactly two cycles of the collection. In addition, it must be possible to

prescribe an orientation to each cycle so that each edge is traversed in

both ways.

We plan to define the class of weakly robust trigraphs and prove that a

connectivity augmentation conjecture for this class implies general

directed cycle double cover conjecture.

This is joint work with Martin Loebl.

Series: Graph Theory Seminar

This talk is a sequel to the speaker's previous lecture given in

the January 31st Combinatorics Seminar, but attendance at the first talk is

not assumed. We begin by carefully reviewing our generalized cycle-cocyle

reversal system for partial graph orientations. A self contained

description of Baker and Norin's Riemann-Roch formula for graphs is given

using their original chip-firing language. We then explain how to

reinterpret and reprove this theorem using partial graph orientations. In

passing, the Baker-Norin rank of a partial orientation is shown to be one

less than the minimum number of directed paths which need to be reversed in

the generalized cycle-cocycle reversal system to produce an acyclic partial

orientation. We conclude with an overview of how these results extend to

the continuous setting of metric graphs (abstract tropical curves).

the January 31st Combinatorics Seminar, but attendance at the first talk is

not assumed. We begin by carefully reviewing our generalized cycle-cocyle

reversal system for partial graph orientations. A self contained

description of Baker and Norin's Riemann-Roch formula for graphs is given

using their original chip-firing language. We then explain how to

reinterpret and reprove this theorem using partial graph orientations. In

passing, the Baker-Norin rank of a partial orientation is shown to be one

less than the minimum number of directed paths which need to be reversed in

the generalized cycle-cocycle reversal system to produce an acyclic partial

orientation. We conclude with an overview of how these results extend to

the continuous setting of metric graphs (abstract tropical curves).

Series: Graph Theory Seminar

Consider a graph G and a specified subset A of vertices. An A-path is a path with both ends in A

and no internal vertex in A. Gallai showed that there exists a min-max formula for the maximum number of pairwise disjoint

A-paths. More recent work has extended this result, considering disjoint A-paths which satisfy various additional properties.

and no internal vertex in A. Gallai showed that there exists a min-max formula for the maximum number of pairwise disjoint

A-paths. More recent work has extended this result, considering disjoint A-paths which satisfy various additional properties.

We consider the following model. We are given a list of {(s_i, t_i): 0< i < k} of pairs of vertices in A, consider

the question of whether there exist many pairwise disjoint A-paths P_1,..., P_t such that for all j,

the ends of P_j are equal to s_i and t_i for some value i. This generalizes the disjoint paths problem and is NP-hard

if k is not fixed. Thus, we cannot hope for an exact min-max theorem. We further restrict the question, and ask if there

either exist t pairwise disjoint such A-paths or alternatively, a bounded set of f(t) vertices intersecting all such paths. In

general, there exist examples where no such function f(t) exists; we present an exact characterization of

when such a function exists.

This is joint work with Daniel Marx.

Series: Graph Theory Seminar

An r-unform n-vertex hypergraph H is said to have the

Manickam-Miklos-Singhi (MMS) property if for every assignment of

weights to

its vertices with nonnegative sum, the number of edges whose total

weight

is nonnegative is at least the minimum degree of H. In this talk I will

show that for n>10r^3, every r-uniform n-vertex hypergraph with equal

codegrees has the MMS property, and the bound on n is essentially

tight up

to a constant factor. An immediate corollary of this result is the

vector

space Manickam-Miklos-Singhi conjecture which states that for n>=4k

and any

weighting on the 1-dimensional subspaces of F_q^n with nonnegative

sum, the

number of nonnegative k-dimensional subspaces is at least ${n-1 \brack

k-1}_q$. I will also discuss two additional generalizations, which

can be

regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting

families. This is joint work with Benny Sudakov.

Manickam-Miklos-Singhi (MMS) property if for every assignment of

weights to

its vertices with nonnegative sum, the number of edges whose total

weight

is nonnegative is at least the minimum degree of H. In this talk I will

show that for n>10r^3, every r-uniform n-vertex hypergraph with equal

codegrees has the MMS property, and the bound on n is essentially

tight up

to a constant factor. An immediate corollary of this result is the

vector

space Manickam-Miklos-Singhi conjecture which states that for n>=4k

and any

weighting on the 1-dimensional subspaces of F_q^n with nonnegative

sum, the

number of nonnegative k-dimensional subspaces is at least ${n-1 \brack

k-1}_q$. I will also discuss two additional generalizations, which

can be

regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting

families. This is joint work with Benny Sudakov.

Series: Graph Theory Seminar

By the 4-color theorem, every planar graph on n vertices has

an independent set of size at least n/4. Finding a simple

proof of this fact is a long-standing open problem.

Furthermore, no polynomial-time algorithm to decide whether

a planar graph has an independent set of size at least (n+1)/4

is known.

an independent set of size at least n/4. Finding a simple

proof of this fact is a long-standing open problem.

Furthermore, no polynomial-time algorithm to decide whether

a planar graph has an independent set of size at least (n+1)/4

is known.

We study the analogous problem for triangle-free planar graphs.

By Grotzsch' theorem, each such graph on n vertices has an

independent set of size at least n/3, and this can be easily

improved to a tight bound of (n+1)/3. We show that for every k,

a triangle-free planar graph of sufficiently large tree-width has

an independent set of size at least (n+k)/3, thus giving a polynomial-time

algorithm to decide the existence of such a set. Furthermore,

we show that there exists a constant c < 3 such that every planar graph

of girth at least five has an independent set of size at least n/c.Joint work with Matthias Mnich.

Series: Graph Theory Seminar

While Robertson and Seymour showed that graphs are

well-quasi-ordered under the minor relation, it is well known

that directed graphs are not. We will present an exact

characterization of the minor-closed sets of directed graphs

which are well-quasi-ordered. This is joint work with M.

Chudnovsky, S. Oum, I. Muzi, and P. Seymour.

well-quasi-ordered under the minor relation, it is well known

that directed graphs are not. We will present an exact

characterization of the minor-closed sets of directed graphs

which are well-quasi-ordered. This is joint work with M.

Chudnovsky, S. Oum, I. Muzi, and P. Seymour.

Series: Graph Theory Seminar

We prove the dcdc conjecture in a class of lean fork graphs, argue that this

class is substantial and show a path towards the complete solution. Joint work with Andrea Jimenez.

class is substantial and show a path towards the complete solution. Joint work with Andrea Jimenez.

Series: Graph Theory Seminar

A systematic study of large combinatorial objects has recently led

to discovering many connections between discrete mathematics and

analysis. In this talk, we apply analytic methods to permutations.

In particular, we associate every sequence of permutations

with a measure on a unit square and show the following:

if the density of every 4-element subpermutation in a permutation p

is 1/4!+o(1), then the density of every k-element subpermutation

is 1/k!+o(1). This answers a question of Graham whether quasirandomness

of a permutation is captured by densities of its 4-element subpermutations.

to discovering many connections between discrete mathematics and

analysis. In this talk, we apply analytic methods to permutations.

In particular, we associate every sequence of permutations

with a measure on a unit square and show the following:

if the density of every 4-element subpermutation in a permutation p

is 1/4!+o(1), then the density of every k-element subpermutation

is 1/k!+o(1). This answers a question of Graham whether quasirandomness

of a permutation is captured by densities of its 4-element subpermutations.

The result is based on a joint work with Oleg Pikhurko.

Series: Graph Theory Seminar

Since the foundational results of Thomason and

Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has

been a lot of effort by many researchers to extend the theory to

hypergraphs. I will present some of this history, and then describe our

recent results that provide such a generalization and unify much of the

previous work. One key new aspect in the theory is a systematic study of

hypergraph eigenvalues first introduced by Friedman and Wigderson. This

is joint work with John Lenz.

Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has

been a lot of effort by many researchers to extend the theory to

hypergraphs. I will present some of this history, and then describe our

recent results that provide such a generalization and unify much of the

previous work. One key new aspect in the theory is a systematic study of

hypergraph eigenvalues first introduced by Friedman and Wigderson. This

is joint work with John Lenz.