If you

Subscribe to the ACO seminar mailing list

Title:Packing in Multipartite Graphs

Speaker: Ryan Martin, Iowa State

When: May 2, 11:30-12:30 (IRREGULAR DAY AND TIME)

Where: HBH 237 (IRREGULAR PLACE)

Abstract:

Speaker: Ryan Martin, Iowa State

When: May 2, 11:30-12:30 (IRREGULAR DAY AND TIME)

Where: HBH 237 (IRREGULAR PLACE)

Abstract:

We present some results on packing graphs in dense multipartite graphs.
This is a question very similar to the Hajnal-Szemer\'edi theorem, which
gives sufficient minimum-degree conditions for an $n$-vertex graph to have a
subgraph consisting of $\lfloor n/r\rfloor$ vertex-disjoint copies of $K_r$.
This is a packing, or tiling, of the graph by copies of $K_r$. The
Hajnal-Szemer\'edi theorem has been generalized to finding minimum-degree
conditions that guarantee packings of non-complete graphs, notably by Alon
and Yuster and by K\"uhn and Osthus.
We consider a multipartite version of this problem. That is, given an
$r$-partite graph with $N$ vertices in each partition, what is the
minimum-degree required of the bipartite graph induced by each pair of
color-classes so that the graph contains $N$ vertex-disjoint copies of
$K_r$? The question has been answered for $r=3,4$, provided $r$ is
sufficiently large. When $r=3$ and $N$ is sufficiently large, a degree
condition of $(2/3)N$ is sufficient with the exception of a single
tripartite graph when $N$ is an odd multiple of $3$. When $r=4$ and $N$ is
sufficiently large, a degree condition of $(3/4)N$ is sufficient and there
is no exceptional graph. There are also bounds on the degree condition for
higher $r$ by Csaba and Mydlarz.
This question has also been generalized to finding minimum-degree conditions
for packings of some arbitrary $r$-colorable graph in an $r$-partite. The
case $r=2$ is highly nontrivial for packing arbitrary bipartite graphs and
was answered very precisely by Zhao. The case $r=3$ is even more complex
and we provide some tight bounds on the required degree condition.
This talk includes joint work with Cs. Magyar, with E. Szemer\'edi and with
Y. Zhao.

Title: Scarf's Lemma and the Stable Paths Problem

Speaker: Penny Haxell, Waterloo

When: May 1, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Penny Haxell, Waterloo

When: May 1, 12:30-13:30

Where: Porter Hall 125B

Abstract:

We address a question in graphs called the stable paths problem, which
is an abstraction of a network routing problem concerning the Border
Gateway Protocol (BGP). The main tool we use is Scarf's Lemma.
This talk will describe Scarf's
Lemma and how it is related to other results more familiar to
combinatorialists, and then will explain its implications for the
stable paths problem.

Title: The formulation complexity of minimum cut

Speaker: Ojas Parekh, Emory University

When: April 24, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Ojas Parekh, Emory University

When: April 24, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Our focus in this talk will be the size of linear programming
formulations of combinatorial optimization problems. We may view this
parameter as akin to traditional measures of complexity, such as
computational time and space. We will focus on problems in P, in
particular the minimum cut problem.
For a graph $(V,E)$, existing linear formulations for the minimum cut
problem require $\Theta(|V||E|)$ variables and constraints. These
formulations can be interpreted as a composition of $|V|-1$ polyhedra
for minimum $s$-$t$ cuts paralleling early algorithmic approaches to
finding globally minimum cuts, which relied on $|V|-1$ calls to a
minimum $s$-$t$ cut algorithm. We present the first formulation to
beat this bound, one that uses $O(|V|^2)$ variables and
$O(|V|^3)$ constraints. Our formulation directly implies a smaller
compact linear relaxation for the Traveling Salesman Problem that is
equivalent in strength to the standard subtour relaxation.

Title: A Polynomial Bound on Vertex Folkman Numbers

Speaker: Andrzej Dudek, Emory University

When:Tuesday April 15, 12:30-13:30 (IRREGULAR DAY)

Where: Wean Hall 5304 (NEW ROOM)

Abstract:

Speaker: Andrzej Dudek, Emory University

When:Tuesday April 15, 12:30-13:30 (IRREGULAR DAY)

Where: Wean Hall 5304 (NEW ROOM)

Abstract:

In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H,
i.e., the order of H is bounded by an iterated power function of n.
In this talk we will give an alternative proof of Folkman's theorem with the relatively small order of H bounded from above by O(n^3\log^3 n).
This is joint work with Vojtech Rodl.

Title: Digraph limits

Speaker: David Offner, CMU

When: April 10, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: David Offner, CMU

When: April 10, 12:30-13:30

Where: Porter Hall 125B

Abstract:

In 2004 Lovasz and Szegedy introduced "graph limits" as follows: "If a sequence of dense graphs G_n has the property that for every fixed F the number of copies of F in G_n tends to a limit, it is possible to define a limit object, namely a symmetric measurable function W:[0,1]2 --> [0,1] called a graphon."
In a 2007 paper, Borgs, Chayes, Lovasz, Sos, and Vesztergombi proved that the space of graphons has a number of nice properties. The main work involved showing that if two graphons are close in the so-called cut norm then their subgraph densities are close, and vice-versa.
In the talk we define a corresponding limit object for directed graphs and show that some analogous theorems hold for these objects.

Title: Two results in Discrete Differential Geometry

Speaker: Aaron Trout, Chatham University

When: April 3, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Aaron Trout, Chatham University

When: April 3, 12:30-13:30

Where: Porter Hall 125B

Abstract:

We will discuss two results in discrete differential geometry: 1) A combinatorial 3-manifold with edges of degree at most five has edge-diameter at most five. 2) Suppose such a combinatorial 3-manifold $M$ has vertices $v$ and $w$ at the maximum edge-distance. Then, $M$ is a 3-sphere whose triangulation is completely determined by the star of $v$. These theorems are analogous to two important results in the differential geometry of positively curved spaces. The first is analogous to the Bonnet-Myers theorem, which bounds the diameter of Riemannian manifolds whose Ricci curvature is everywhere greater than a fixed positive constant. The second result is a discrete version of the Toponogov-Cheng rigid-sphere theorem, which shows that the maximum diameter allowed by the Bonnet-Myers theorem is achieved only for the standard sphere. The proofs we present are entirely combinatorial in nature, use only elementary arguments, and follow closely the proofs of the corresponding classical results. We will also talk about some enumeration algorithms which can be used to investigate the geometry of combinatorial manifolds.
This talk is based on my Ph.D. thesis, which was done at Rice University under the direction of Robin Forman.

Title:Intersection Cuts in 2 Dimensions

Speaker: Francois Margot, CMU

When: March 27, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Francois Margot, CMU

When: March 27, 12:30-13:30

Where: Porter Hall 125B

Abstract:

When solving Mixed Integer Linear Programs (MILP) with branch-and-cut
algorithms a variety of cuts can be generated. The best known cuts are
probably Gomory mixed integer cuts, obtained from a single row
of the optimal simplex tableau for the linear relaxation of the MILP.
Recently, results on generating cuts using information from two rows
of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and
Weismantel (2007) investigate the facets of a particular relaxation of the
MILP to a problem with two integer variables and two constraints. They show
that all facets are then split inequalities or intersection cuts obtained
from triangles or quadrilaterals. We give the converse, determining which
of these splits, triangles and quadrilaterals actually give facets.
We also give the corresponding characterization for an infinite-dimensional
relaxation of the relaxation of Andersen et al., similarly to the
relaxation used by Gomory and Johnson in their study of the group problem.
Joint work with Gerard Cornuejols.

Title: Coloring triangle-free graphs on surfaces

Speaker: Robin Thomas, Georgia Tech

When: February 28, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Robin Thomas, Georgia Tech

When: February 28, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Let S be a fixed surface, and let k and q be fixed integers. Is there
a polynomial-time algorithm that decides whether an input graph of girth
at least q drawn in S is k-colorable? This question has been studied
extensively during the last 15 years. In the first part of the talk we
will survey known results.
In the second part of the talk we describe a solution to one of the
two cases left open (the prospects for the other one are not bright).
For every surface S we give a polynomial-time algorithm that computes
the chromatic number of an input triangle-free graph G drawn in S. The new
contribution here is deciding whether G is 3-colorable, and is obtained
using a coloring extension theorem that in turn makes use of disjoint
paths in order to construct a coloring. The notion of "winding number" of
a 3-coloring plays an important role. This is joint work with Zdenek Dvorak
and Daniel Kral.

Title: An Erdos-Stone type theorem for spanning subgraphs

Speaker: Anusch Taraz

When: February 21, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Anusch Taraz

When: February 21, 12:30-13:30

Where: Porter Hall 125B

Abstract:

In this talk we discuss the proof of the following conjecture by Bollobas and Komlos: Suppose that G and H are both graphs on n vertices, H has bounded maximum degree, chromatic number r, and bandwidth o(n), G has minimum degree at least ((r-1)/r + eps)n, and n is sufficiently large. Then G must contain a copy of H. This is joint work with Julia Boettcher and Mathias Schacht.

Title: Avoiding small subgraphs in Achlioptas processes

Speaker: Michael Krivelevich, Tel Aviv University

When: February 14, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Michael Krivelevich, Tel Aviv University

When: February 14, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Consider the following model of random graphs. We are given a
monotone graph property P (Hamiltonicity, non-3-colorability,
containment of a copy of a fixed graph H etc.) and an integer
parameter r>=1. At each round, we are presented with r random
edges from the set of edges of the complete graph K_n on n
vertices and are asked to choose one of them. The task is to
design an online edge choice algorithm that will be able to
postpone (avoid) or to facilitate (embrace) almost surely the
appearance of P. This model is sometimes called the Achlioptas
process, after Dimitris Achlioptas who suggested it for the
case r=2 and the property P being the existence of a linear sized
connected component (the so called giant component) in the graph.
The latter setting is essentially the only one that has been
studied extensively so far.
In the work to be presented, we were able to achieve a satisfactory
solution for the case where the task is to avoid the appearance of
a fixed graph H, and H is either a cycle, or a complete graph, or
a complete bipartite graph. The answer is quite surprising and
depends heavily on the parameter r. For example, the threshold for
avoiding K_4 in the Achlioptas process with parameter r=2 is
n^{28/19}.

Title: Lehman Matrices

Speaker: Gerard Cornuejols

When: February 7, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Gerard Cornuejols

When: February 7, 12:30-13:30

Where: Porter Hall 125B

Abstract:

A pair of square $0,1$ matrices $A,B$ such that $AB^T=E+kI$ (where $E$
is the $n \times n$ matrix of all 1s and $k$ is a positive integer) are
called {\em Lehman matrices}. These matrices figure prominently in
Lehman's seminal theorem on minimally nonideal matrices. There are two
choices of $k$ for which this matrix equation is known to have infinite
families of solutions. When $n=k2+k+1$ and $A=B$, we get point-line
incidence matrices of finite projective planes, which have been widely
studied in the literature. The other case occurs when $k=1$ and $n$ is
arbitrary, but very little is known in this case. This talk discusses
this class of Lehman matrices and classifies them according to their
similarity to circulant matrices. The work is joint with Betrand Guenin
and Levent Tuncel.

Title:On conditional sorting

Speaker: Victor Grinberg

When: January 31, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Speaker: Victor Grinberg

When: January 31, 12:30-13:30

Where: Porter Hall 125B

Abstract:

Let P be a finite poset and s(P) the minimal number of
pairwise comparisons, which will suffice to sort P in the worst case. A
sorting
procedure can be viewed as a game, where a PLAYER chooses a pair of
non-comparable elements, and an ORACLE responds which one is smaller. The
game ends when a linear order is achieved. The PLAYER tries to minimize the
number of questions, the ORACLE --- to maximize it. s(P) is the price of
this game.
Conditional sorting is a generalization of this (conventional)
sorting. In it, the ORACLE is restricted in his answers: they must comply with
a given poset Q that is an extension of P. Let s(P/Q) be the price of
this game. Clearly, s(P/P)=s(P) and s(Q){\leq} s(P/Q){\leq} s(P).
Conditional sorting can be used to obtain nontrivial lower bounds for
conventional sorting (an old idea of D. Knuth).
For the case when P is an extension of 2 chains (merging), we demonstrate an
intimate connection between
conditional and conventional sorting. In this
case, for any extension Q an
"intermediate" poset R can be effectively
found such that s(P/Q)=s(R).

Title: Packing cubes in a torus

Speaker: Tom Bohman

When: January 24, 12:30-13:30

Where: Doherty Hall 4303

Abstract:

Speaker: Tom Bohman

When: January 24, 12:30-13:30

Where: Doherty Hall 4303

Abstract:

We consider the following packing problem. How many
d-dimensional cubes of side length 2 can we pack into
a d-dimensional torus of odd side length? In this
talk we present some of the best known constructions,
detail the connection between this packing problem
and the problem of determining the Shannon capacities
of graphs, and discuss some recent techniques for
establishing upper bounds. Some related open
questions on graph products will also be discussed.

Title: Induced subgraphs with distinct size or order

Speaker: Alexander Kostochka, University of Illinois at Urbana-Champaign

When: December 6, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Alexander Kostochka, University of Illinois at Urbana-Champaign

When: December 6, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Click here

Title: Log-Concave Random Graphs

Speaker: Alan Frieze

When: November 29, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Alan Frieze

When: November 29, 16:30-17:30

Where: Wean Hall 5302

Abstract:

We propose the following model of a random graph on n vertices.
Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for
every pair ij with 1 \le i,j \le n. Then G_{F,p} is the
distribution on graphs with n vertices obtained by picking a
random point X from a distribution with a log-concave density f and
defining a graph on n vertices whose edges
are pairs ij for which X_{ij} \le p. The standard Erdos-Renyi
model is the special case when F is the indicator function for the
We thus obtain an interesting connection between convex geometry and
random graphs.

When f is down-monotone we can determine the connectivity and matching thresholds up to a constant factor. When f is the indicator function for a right simplex then we can obtain more precise results on connectivity and the diameter.

If X is used to define weights for an optimization problem and f is "column independent" then we can whp solve the ATSP asymptotically.

Joint work with Santosh Vempala and Juan Vera

Title: On subword containment

Speaker: Irina Gheorghiciuc

When: November 15, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Irina Gheorghiciuc

When: November 15, 16:30-17:30

Where: Wean Hall 5302

Abstract:

We consider words with letters from a q-ary
alphabet A. The k-th subword complexity of a word w in A* is the
number of distinct subwords of length k that appear as contiguous
subwords of w.

We analyze subword complexity from both combinatorial and probabilistic viewpoints. Our first main result is a precise analysis of the expected k-th subword complexity of a randomly-chosen word w in A^n. Our other main result describes, for w in A*, the degree to which one understands the set of all subwords of w, provided that one knows only the set of all subwords of some particular length k. This is joint work with Mark Ward.

Title: Local anti-Ramsey numbers

Speaker: Tao Jiang (Miami University, Oxford, OH)

When: November 8, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Tao Jiang (Miami University, Oxford, OH)

When: November 8, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Anti-Ramsey problems usually refer to the study of rainbow subgraphs
in an edge-colored host graph, where a subgraph is rainbow if all
of its edges have different colors. The anti-Ramsey number of a graph
H for a given integer n, denoted by AR(n,H), is the maximum
number of colors of an edge-coloring of the complete graph K_n
that contrains no rainbow copy of H. The idea is that as one
increases the overall number of colors used on K_n, eventually
one must force a rainbow copy of H. This can be viewed as Turan
analogue for edge-colorings. The anti-Ramsey numbers were introduced
by Erdos, Simonovits, and Sos in the 1970's. Many news results
were obtained in recent years.

Axenovich, Jiang, Tuza introduced the notion of local anti-Ramsey numbers. The goal is to study the threshold on the number of colors appearing at each vertex beyond which a rainbow copy of H is forced. They also considered properly colored copy of H. Several problems they raised remain unsolved. The main difficulty seems to be that when one imposes a condition on the color degree (the number of different colors appearing at a vertex) it has little global effect, and often one gets closer to extremal values by using highly unbalanced colorings. So, most techniques based on counting seem to fail. In this seminar talk, we review these problems and the partial results. We answer one of the conjectures raised by them affirmatively. That is, for every k, there exists an absolutely constant lambda_k such that in every edge-coloring of K_n in which the color degree of each vertex is at least lambda_k, there exists a properly cycle of length exactly k.

Axenovich, Jiang, Tuza introduced the notion of local anti-Ramsey numbers. The goal is to study the threshold on the number of colors appearing at each vertex beyond which a rainbow copy of H is forced. They also considered properly colored copy of H. Several problems they raised remain unsolved. The main difficulty seems to be that when one imposes a condition on the color degree (the number of different colors appearing at a vertex) it has little global effect, and often one gets closer to extremal values by using highly unbalanced colorings. So, most techniques based on counting seem to fail. In this seminar talk, we review these problems and the partial results. We answer one of the conjectures raised by them affirmatively. That is, for every k, there exists an absolutely constant lambda_k such that in every edge-coloring of K_n in which the color degree of each vertex is at least lambda_k, there exists a properly cycle of length exactly k.

Title: Graphs containing triangles are not 3-common

Speaker: Michael Young

When: November 1, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Michael Young

When: November 1, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Jagger, Stovicek and Thomason defined the class of k-common
graphs, and showed among other results that every graph containing K_4 as
a subgraph is not 2-common. We prove that every graph containing K_3 as
a subgraph is not 3-common.

Title: The Directed Orienteering Problem

Speaker: Viswanath Nagarajan

When: October 25, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Viswanath Nagarajan

When: October 25, 16:30-17:30

Where: Wean Hall 5302

Abstract:

We consider the orienteering problem on asymmetric metrics: given a directed metric (V,d), a starting vertex
s, an ending vertex t, and a length bound D, find an s-t path having length at most D that
maximizes
the number of vertices covered. We give an approximation algorithm for this problem achieving a guarantee of
O(log^2 n). The previously best known result was an O(log n)-approximation algorithm that runs in
quasi-polynomial time (Chekuri & Pal '05). For the undirected special case of this problem, a 3-approximation
algorithm was known (Bansal et al. '04). Our result answers positively the question of poly-logarithmic
approximability of the directed orienteering problem (Blum et al. '03).
This is joint work with R. Ravi.

Title: On a random graph evolving by degrees

Speaker: Boris Pittel (Ohio State University)

When: October 19, 15:30-16:30**!! Non-standard day/time !!**

Where: Wean Hall 5302

Abstract:

Speaker: Boris Pittel (Ohio State University)

When: October 19, 15:30-16:30

Where: Wean Hall 5302

Abstract:

Click here

Title: The Typical Structure of Graphs without Given Excluded Subgraphs

Speaker: Jozsi Balogh, University of Illinois at Urbana-Champaign

When: October 11, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Speaker: Jozsi Balogh, University of Illinois at Urbana-Champaign

When: October 11, 16:30-17:30

Where: Wean Hall 5302

Abstract:

Let L be a finite family of graphs. We describe the typical
structure of L-free graphs, improving our earlier results on the
Erdos-Frankl-Rodl theorem, by proving our conjecture from our
earlier paper. Let p=p(L)=min{F\in L:\chi(F)-1}. We
shall prove that the structure of almost all L-free graphs are very
similar to the Turan graph T_{n,p}, where ``similarity'' is measured
in terms of graph theoretical parameters of L.
Some more recent developements will be discussed as well.
Joint work with B. Bollobas and M. Simonovits.

Title: Eigenvalues and discrepancy

Speaker: Amin Coja-Oghlan (Humboldt University, Berlin)

When: October 4, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

Speaker: Amin Coja-Oghlan (Humboldt University, Berlin)

When: October 4, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

A graph G has ``low discrepancy'' if the global distribution of the edges of G resembles the edge distribution
of
a random graph of the same density. Moreover, G has a ``large spectral gap'' if the second largest eigenvalue
of
the adjacency matrix of G (or another suitable matrix representation of G) is significantly smaller than the
average degree. It is well known (and easy to see) that a graph with a large spectral gap has low discrepancy.
In
this talk I will investigate the converse implication in the case of sparse graphs. The main result is that low
discrepancy implies that G ``essentially'' has a large spectral gap. The talk is based on a joint paper with
Noga
Alon, Hiep Han, Mihyun Kang, Vojtech Rodl, and Mathias Schacht.

Title: Hamilton cycles and perfect matchings in hypergraphs

Speaker: Andrzej Rucinski (Adam Mickiewicz University, Poznan)

When: September 27, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

Speaker: Andrzej Rucinski (Adam Mickiewicz University, Poznan)

When: September 27, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

A classic theorem of Dirac states that a sufficient condition for an n-vertex graph to be
hamiltonian is that the minimum degree is at least n/2.
In my talk I will present recent results on Dirac type problems for k-uniform hypergraphs, obtained jointly with
V. Rödl and E. Szemerédi.

Title: PageRank and the Random Surfer Model

Speaker: Páll Melsted

When: September 20, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

Speaker: Páll Melsted

When: September 20, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

In recent years there has been considerable interest in analyzing random graph models for the
Web. We consider two such models - the Random Surfer model introduced by Blum et al. and
the PageRank-based selection model proposed by Pandurangan et al.. It has been observed
that search engines influence the growth of the Web. The PageRank-based selection model tries
to capture the effect that these search engines have on the growth of the Web by adding new links
according to Pagerank. The PageRank algorithm is used in the Google search engine for ranking
search results.

We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it also follows the same powerlaw as the expected degree.

We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

This is joint work with Prasad Chebolu.

We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it also follows the same powerlaw as the expected degree.

We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

This is joint work with Prasad Chebolu.

Title:Quadruple systems with independent neighborhoods

Speaker: Dhruv Mubayi

When: September 13, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

Speaker: Dhruv Mubayi

When: September 13, 16:30-17:30pm

Where: Wean Hall 5302

Abstract:

What is the maximum number of edges in a k-uniform hypergraph on n
vertices whose neighborhoods are all independent sets? When k=2 the
answer is n^2/4 and this was proved by Mantel in 1907. The next case k=3
was solved by Furedi-Pikhurko-Simonovits in 2003. I will present a proof
for the case k=4. This is joint work with Zoltan Furedi and Oleg Pikhurko.

Title: Two applications of Szemeredi's Regularity Lemma

Speaker: Oleg Pikhurko

When: September 6, 15:30-16:30pm

Where: Wean Hall, Room 5310

Abstract:

Speaker: Oleg Pikhurko

When: September 6, 15:30-16:30pm

Where: Wean Hall, Room 5310

Abstract:

I will present two (short and unrelated) applications of Szemeredi's
Regularity Lemma.

In one (joint work with Benny Sudakov) we prove, for all large n, the conjecture of Lazebnik (1989) that among all graphs with n vertices and m < n^2/4 edges the maximum number of 3-colorings is achieved by a semi-complete biparite graph.

Another application proves the conjecture of Aigner, Triesch, and Tuza (1995) that one can find an unknown acyclic orientation of any given graph of order n by quering at most (1/4+o(1))n^2 edges.

In one (joint work with Benny Sudakov) we prove, for all large n, the conjecture of Lazebnik (1989) that among all graphs with n vertices and m < n^2/4 edges the maximum number of 3-colorings is achieved by a semi-complete biparite graph.

Another application proves the conjecture of Aigner, Triesch, and Tuza (1995) that one can find an unknown acyclic orientation of any given graph of order n by quering at most (1/4+o(1))n^2 edges.

PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.