The ACO seminar (2002-2003)

Schedule:

TITLE: Exact Covers and Their Consequences.
SPEAKER: Miklos Ruszinko
WHEN: Thursday, Oct. 3 , 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:
ABSTRACT:

Let $p$ be a positive integer and let $Q$ be a subset of $\{0,1,\dots ,p\}$. Call $p$ sets $A_1,A_2,\dots ,A_p$ of a ground set $X$ a $(p,Q)$-system if the number of sets $A_i$ containing $x$ is in $Q$ for every $x\in X$. In hypergraph terminology, a $(p,Q)$-system is a hypergraph with $p$ edges such that each vertex $x$ has degree $d(x)\in Q$. A family of sets ${\cal F}$ with ground set $X$ is called $(p,Q)$-free if no $p$ sets of ${\cal F}$ form a $(p,Q)$-system on $X$. We address the Tur\'an type problem for $(p,Q)$-systems: $f(n,p,Q)$ is defined as $\max |{\cal F}|$ over all $(p,Q)$-free families on the ground set $[n]=\{1,2,\dots ,n\}$.

We study the behavior of $f(n,p,Q)$ when $p$ is fixed (allowing $2^{p+1}$ choices for $Q$) while $n$ tends to infinity. The new results of this paper mostly relate to the middle zone where $2^{n-1}\le f(n,p,Q) \le (1-c)2^n$ (in this upper bound $c$ depends only on $p$). This direction was initiated by Paul Erd\H os who asked about the behavior of $f(n,4,\{0,3\})$. In addition we give a brief survey on results and methods (old and recent) in the low zone (where $f(n,p,Q)=o(2^n)$) and in the high zone (where $2^n-(2-c)^n < f(n,p,Q)$). The results were obtained by Zolt\'an F\"uredi, Andr\'as Gy\'arf\'as and Mikl\'os Ruszink\'o.

We also give an application of these families where we solve a geometry problem posed by Levon Khachatrian.

TITLE: Long paths in line arrangements
SPEAKER: Cliff Smyth
WHEN: Thursday, Oct. 10, 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:
ABSTRACT:

Consider an arrangement $A$ of $n$ lines in the plane with none vertical. An ($x$-)monotone path through $A$ is intuitively defined as a path constructed in the following way. Start at some point on some line $l$ in $A$ and then walk along $l$ so that your $x$-coordinate is increasing. Whenever you encounter an intersection with another line $l'$ of $A$, you may either continue walking along the current line $l$ or turn and start walking along $l'$, again always being sure to walk with increasing $x$-coordinate. The length of the path is defined to be the number of turns made plus $1$ or the number of line segments used.

Let $l(A)$ be the maximum length of a monotone path through $A$. $l(A)$ can be viewed as the maximum combinatorial complexity of a $y$-convex region as such that would arise in some topological sweep of the cells determined by $A$. Let $l(n)$ be the maximum of $l(A)$ over all $n$-line arrangments $A$. Trivially $l(n) = O(n^2)$. The main conjecture is that $l(n) = o(n^2)$. Arrangements $A$ with $l(A) = \Omega(n^{3/2}), \Omega(n^{5/3})$, and $\Omega(n^{7/4})$ have been constructed by Sharir, Matou\v{s}ek, and Radoi\v{c}i\'{c} and T\'{o}th respectively.

For every $\epsilon > 0$ we construct arrangements $A$ with $l(A) = \Omega(n^{2 - \epsilon})$. Our methods also give lower bounds of the form $n^{2 - o(n)}$.

This is joint work with Oded Regev and J\'oszef Balogh.

TITLE: Random Satisfiable 3CNF formulas
SPEAKER: Abie Flaxman
WHEN: Thursday, Nov. 7, 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:

• A. Flaxman, A spectral technique for random satisfiable 3CNF formulas
• M. Alekhnokich and E. Ben-Sasson, Analysis of the Random Walk Algorithm on Random 3-CNFs

Testing the satisfiability of 3CNF formulas is the canonical NP-complete problem. Vast amounts of recent work have focused on the most natural random distribution of 3SAT instances, in which $m$ clauses are choosen uniformly at random. This talk will address the second most natural random distribution of 3SAT instances, where $m$ clauses are choosen at random, uniformly from the clauses which satisfy a particular assignment $\phi$.

The central question is "how hard is it to find a satisfying assignment without knowledge of the 'planted' satisfying assignment $\phi$?" The answer, to be elaborated in the talk, is: not hard if $m$ is larger than $C n$, where $n$ is the number of variables, but only if you know how to do it. In particular, we will show that an algorithm based on a graph coloring algorithm of Alon and Kahale works and an algorithm based on random walks does not.

Some of this is original work, some is from Alekhnokich and Ben-Sasson, Analysis of the Random Walk Algorithm on Random 3-CNFs.

TITLE: How many random edges make a dense graph hamiltonian?
SPEAKER: Ryan Martin
WHEN: Thursday, Nov. 21, 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:
ABSTRACT: See title.

Joint work with Alan Frieze and Tom Bohman.

TITLE: Covering graphs using Trees and Stars
SPEAKER: Amitabh Sinha
WHEN: Thursday, Dec. 5, 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:
ABSTRACT:

A tree cover of a graph $G$ is defined as a collection of trees such that their union includes all the vertices of $G$. The weight of a tree cover is the weight of the maximum weight tree in the tree cover. Given a positive integer $k$, the $k$-tree cover problem is to compute a minimum cost tree cover which has no more than $k$ trees. Star covers are defined analogously. Additionally, we may also be provided with a set of $k$ vertices which are to serve as roots of the trees or stars. In this paper, we provide constant factor approximation algorithms for finding tree and star covers of graphs, in the rooted and unrooted versions.

Joint work with Guy Even, Naveen Garg, Jochen Konemann and R. Ravi.

TITLE: TBA
SPEAKER: Venk Natarajan
WHEN: Thursday, Dec. 12, 12:15pm-1:15pm.
WHERE: Wean 7220.
PAPERS:
ABSTRACT:

Back to the ACO home page