SCIENTIFIC PROGRAMS AND ACTIVITIES

March 19, 2024

21-23 May, 2009
Watermellon Workshop on Extremal Graph Theory

University of Waterloo

Abstracts


Intersecting families in random hypergraphs
by
Tom Bohman
, Carnegie Mellon University
-------------------------------------------------------------

Graphs with the epsilon-density property.
by
Andrzej Dudek
Carnegie Mellon University
Coauthors: Peter Frankl and Vojta Rödl

In this talk we will mainly present some Ramsey-type results for bipartite graphs.

For a given bipartite graph G we write R? G and say that a bipartite graph R has the induced eps-density property if every subgraph of R with at least eps|E(R)| edges contains a copy of G which is an induced subgraph of R. We show that for every eps, 0 < eps < 1, there is a constant c=c(eps) such that for each n there exists a bipartite graph of order 2cn such that R? G for every bipartite graph G=(V1, V2, E) with |V1|, |V2| = n. This is best possible up to the value of c. Clearly, setting eps=1/r yields that for every integer r there is a constant c=c(r) such that for each n there exists a bipartite graph of order 2cn such that any r-coloring of its edges yields a monochromatic and induced copy of every G=(V1, V2, E) with |V1|, |V2| = n.

In the remaining part of the talk we will discuss similar results for k-partite k-uniform hypergraphs.
--------------------------------------------------------------------------------

The Karp-Sipser Matching Algorithm and refinements
by
Alan Frieze
, Carnegie Mellon University

Karp and Sipser (1981) proposed a simple greedy matching algorithm that they showed to work surprisingly well on sparse random graphs. In addition they showed a remarkable transition in the algorithm's performance at average degree e=2.718.... . In 1998 Aronson,F,Pittel gave a sharper analysis and I will try to give a quick overview of this. More recently, Bohman and F. have applied the algorithm to random graphs with a fixed degree sequence satisfying a
log-concavity condition. We describe how this condition enables one to analyse the K-S algorithm in this context. Finally, A,F,P had shown that whp K-S only makes very few "mistakes" and this raises the possibility of fixing these mistakes via an augmenting path algorithm in o(n) time, making O(n) time altogether. We show how this can be done, in joint work with P. Chebolu and P. Melsted.
-------------------------------------------------------------

Orientability thresholds for random hypergraphs
by
J
ane Gao

-------------------------------------------------------------

Erdös-Ko-Rado theorems
by
Chris Godsil
, University of Waterloo

The Erd\H{o}s-Ko-Rado Theorem tells us that if $\mathcal{F}$ is collection of
$k$-subsets of $V={1,\ldots,v}$ such that any members of $\mathcal{F}$ have at least one point
in common, then \begin{enumerate}[(a)] \item $|\mathcal{F}| \le \binom{v-1}{k-1}$.
\item If equality holds, then $\mathcal{F}$ consists of all $k$-subsets of $V$ that contain some given point $i$ of $V$. \end{enumerate} This is certainly one of the central results in combinatorics.
My aim in this talk is to introduce some of the many analogs of the EKR theorem, and to show how we can use linear algebra to prove them.


-------------------------------------------------------------

Extremal graphs avoiding a certain subdivision of the wheel graph
by
Elad Horev
Department of computer science, Ben-Gurion University, Israel.

For an integer r = 2, let Sr denote the class consisting of subdivisions of the wheel graph with r spokes in which a K1, r is left undivided. Let ex(n, Sr) denote the maximum number of edges of an n-vertex graph containing no Sr-subgraph, and let Ex(n, Sr) denote the class of all n-vertex graphs containing no Sr-subgraph that are of size ex(n, Sr). In this paper, a conjecture is put forth stating that for r = 3 and n = 2r+1, ex(n, Sr) = (r-1) n - é (r-1)(r-3/2) ù and Ex(n, Sr) consists of a single graph which is the graph obtained from Kr-1, n-r+1 by adding a maximum matching to the color class of cardinality r-1. A previous result of C. Thomassen (A minimal condition implying a special K4-subdivision, Archiv. Math., (25) 1974, 210-215), who determined ex(n, S3) and Ex(n, S3), asserts that this conjecture is true for r = 3. In this paper it is shown to hold for r = 4.

In his book, entitled " Extremal Graph Theory ", B. Bollobás, states that for r = 3 and an appropriate n it holds that ex(n, Sr) = (r+1)2r n and states that this bound is not tight. Consequently, Problem 15 page 398 in Bollobás' book, prompts the reader to obtain a better estimation of the function ex(n, Sr). Indeed, techniques used in this paper are sufficient to prove that for r = 4 and n = r+1, ex(n, Sr) = (r || 2) n. However, in a recent work of M. Lomonosov and the author (Structure of r-connected graphs avoiding a certain subdivision of the wheel graph, manuscript) it is established that ex(n, Sr) = Q(rn). This essentially answers the problem of Bollobás.
--------------------------------------------------------------------------------

On Erdos-Ko-Rado Graphs
by
Glenn Hurlbert
Arizona State University
Coauthors: Vikram Kamat

Holroyd, Spencer and Talbot considered the Erdos-Ko-Rado Theorem under the restriction that certain pairs of elements cannot belong to the same set. Given a graph G, let I=Ir(G) be the collection of all independent sets of size r. A star in I is a subfamily containing a common vertex. We say that G has the r-EKR property if every intersecting family in I has at most as many sets as the largest star. Let m=m(G) be the minimum size of a maximum independent set in G. Among other results we prove that if G is a disjoint union of chordal graphs with a least one isolated vertex, then G is r-EKR whenever r = m/2.
--------------------------------------------------------------------------------

List colorings with distinct list sizes, the case of complete bipartite graphs
by
Ida Kantor
Department of Mathematics, University of Illinois at Urbana-Champaign
Coauthors: Zoltán Füredi (Rényi Institute of Mathematics of the Hungarian Academy)

A graph G is f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, csc(G), is the minimum of ?f(v), over all f such that G is f-choosable. We show that csc(G)/|V(G)| can be bounded while the minimum degree dmin(G)? 8. (This is not true for the list chromatic number, cl(G)). Our main tool is to give tight estimates for the sum choice number for the complete bipartite graphs Ka, q.
--------------------------------------------------------------------------------

Algebraic and geometric constructions in extremal combinatorics
by
Felix Lazebnik,
University of Delaware

In the talk I will discuss some examples of applications of algebraic and geometric techniques in extremal combinatorics, mention several recent results, and list some open problems.
--------------------------------------------------------------------------------

Squares in Sumsets
by
Hoi H. Nguyen
Rutgers University, New Brunswick, NJ
Coauthors: Van H. Vu, Rutgers University, New Brunswick, NJ

A finite set A of integers is square-sum-free if there is no subset of A sums up to a square. In 1986, Erdös posed the problem of determining the largest cardinality of a square-sum-free subset of {1, ..., n }. Answering this question, we show that this maximum cardinality is of order n1/3+o(1).
--------------------------------------------------------------------------------

On Even-cycle-free Subgraphs of the Hypercube
by
Lale Özkahya
University of Illinois at Urbana-Champaign
Coauthors: Zoltán Füredi (University of Illinois at Urbana-Champaign)

Given graphs P and Q, the generalized Turan number ex(Q, P) denotes the maximum number of edges of a P-free subgraph of Q. Erdös (1984) conjectured that ex(Qn, C4) = (1/2+o(1))e(Qn), where e(Qn) is the number of edges in the hypercube Qn. Fan Chung showed an upper bound 0.623 e(Qn) and that ex(Qn, C6) = 0.25 e(Qn), moreover that ex(Qn, C4k) = o(e(Qn)) for k = 2. There are further results by Alon et al., Axenovich et al., Thomason et al. and more. We show that ex(Qn, C4k+2) = o(e(Qn)) for k = 3. The case ex(Qn, C10) remains open. This is a joint work with Zoltán Füredi.
--------------------------------------------------------------------------------

Critical Hamilton cycles and perfect matchings on a random geometric graph.
by
Xavier Pérez-Giménez
University of Waterloo
Coauthors: Nick Wormald

We present a strong asymptotic equivalence between the threshold for existence of a Hamilton cycle (or a perfect matching) on a random geometric graph and the threshold for the minimum degree to be 2 (or 1). More precisely, it is shown that the smallest radius that guarantees the existence of k disjoint Hamilton cycles together with q disjoint perfect matchings is asymptotically almost surely exactly the same as the smallest radius for the minimum degree to be 2k+q. This result extends to the setting of random geometric graphs a similar statement which is known to hold for the Erdos-Rényi models.
--------------------------------------------------------------------------------

Maximizing the number of colourings
by
Oleg Pikhurko, Carnegie Mellon University

An old problem of Linial and Wilf asks for $f(n,m,l)$, the maximum number of $l$-colorings that a graph with $n$ vertices and $m$ edges can have. We solve this problem for every fixed $l$ when $C\le m\le cn^2$ for some $C,c>0$ depending on $l$ only. Moreover, for $l=3$, we we establish the structure of optimal graphs for all large $m\le n^2/4$ confirming (in a stronger form) a conjecture of Lazebnik from 1989.

This is joint work with Po-Shen Loh and Benny Sudakov.

--------------------------------------------------------------------------------

Minimal graphs having crossing number at least two
by

Bruce Richter
, University of Waterloo

The study of graphs minimal with crossing number at least 2 has a long and checkered history. The Petersen Graph is one example: its crossing number is 2 and every proper subgraph has crossing number at most 1. Another example is the line graph of K_{3,3}, whose crossing number is 3 and every proper subgraph has crossing number at most 1. It is not known what all the examples are, but in recent work with Bokal, Oporowski and Salazar, we have shown that there is a construction that produces all (3-connected) examples that have more than some number (approximately 10000) vertices. This talk will give an overview of the reduction to the 3- connected case and how the classification is obtained.
--------------------------------------------------------------------------------



--------------------------------------------------------------------------------

Piercing Random Boxes
by
Linh Tran
Rutgers University

Consider a set of n random axis parallel boxes in the unit hypercube in Rd, where d is fixed and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least Wd( vn (logn) d/2-1 ) and at most Od ( vn (logn)d/2-1 loglogn).
------------------------------------------------------------------------
The structural approach to extremal problems in combinatorial number theory

by
Van Vu
, Rutgers University

We discuss a new, general approach to a large collection of problems in combinatorial number theory. The core of this approach are Freiman-type structural theorems, many of which will be presented through the talk. In some sense, this approach has the same spirit as the structural approach in graph theory (ala Robertson-Seymor).

These results have applications in various areas, such as number theory, combinatorics and mathematical physics, some of which solved long standing conjectures. Here are a few recent applications:

(1) If a subset A of {1,2...,n} has more than n^{1/3} log^3 n elements, then some subset of A sums up to a square. (This was conjectured by Erdos in 1986, with partial results by Alon (87), Lipkin (87) Alon-Freiman (88) Sarkozy (93).) This is a result with Hoi Nguyen.

(2) Let p be a large prime. A set B of positive integers is "small" (with respect to p) if the sum of the elements of B is less then p. With Hoi Nguyen and Szemeredi, we showed that if a set A of residues mod p is zero-sum free (i.e., no subsum equals zero), then A is very close to being "small".

(Part of the talk is based on the speaker recent survey, http://front.math.ucdavis.edu/0804.3211, but we will introduce several new results as well.)
--------------------------------------------------------------------------------

Independence number and hadwidger number
by
Hehui Wu
University of Illinois at Urbana, Champaign
Coauthors: Joszef Balogh, John lenz

Given a graph G, the Hadwidger number h(G) is the maximum size of a clique minorof G. Hadwidger conjecture states that h(G) = c(G). Since a(G)c(G) = n(G), a weaker conjecture followed is that h(G) = n(G)/a(G). In this talk, we show that h(G) = n(G)/(2a(G)-O(log(a(G)))), Specifically, we prove h(g) = n/7.6 when a(G)=5 and h(G) = n/(2a(G)-3) when a(G) be a number not less than 7 except 8 or 10. These improve Kawabayashi and Song's result, which is (2a-2)h(g) = n(G).

Back to top