Title: Tracing a single user

A family ${\cal F}$ of subsets of $\{1,2,\ldots,n\}$ is called $r$-single-user tracing superimposed ($r$-SUT) if for all choices of ${\cal F}_1,{\cal F}_2,\ldots,{\cal F}_k \subseteq {\cal F}$ with $1 \leq |{\cal F}_i| \leq r$, $$ \bigcup_{A \in {\cal F}_1} A = \bigcup_{A \in {\cal F}_2} A = \ldots = \bigcup_{A \in {\cal F}_k} A $$ implies $$ \bigcap_{i=1}^k {\cal F}_i \neq \emptyset. $$ That is, given the union of at most $r$ members of ${\cal F}$, one can identify at least one of these members.

This problem is motivated by applications in molecular biology, where, for example, a group of DNA sequences that carry relevant genomic information is under study, and the objective is to find at least one sequence with this information. In this problem a set of $m$ sequences is given, containing at most $r$ positives, i.e. sequences with the required information. In each experiment, a subset of the sequences is tested, and the outcome of the experiment is positive if and only if the subset contains at least one positive sequence. The objective is to find at least one positive sequence by conducting as few experiments as possible, where all the experiments are carried out simultaneously. In such experiments, we can view each of the given DNA sequences as a subset of the experiments (the experiments in which it participates), and in order to be able to identify at least one sequence with the relevant information, we need these subsets to form an $r$-SUT family. See \cite{CR} for further discussion of such applications.

Let $g(n,r)$ denote the maximum possible size of an $r$-SUT family of subsets of $\{1,2,\ldots,n\}$. Thus, $m = g(n,r)$ is the maximum number of DNA sequences for which we can solve the above problem by $n$ experiments.

Cs\H{u}r\"{o}s and Ruszink\'{o} \cite{CR} proved that there exist constants $c_1, c_2 > 0$ such that $$ \frac{c_1}{r^2} \leq \frac{\log g(n,r)}{n} \leq \frac{c_2}{r}. $$ In this work we show that their upper bound is tight up to a constant factor, using a probabilistic argument. We further give an explicit construction for fixed $r$, that is, an algorithm that constructs a family of the required size in time $(g(n,r))^{O(r)}$.

Title: Circular chromatic number of hexagonal chains with orientations

We introduce the (circular) chromatic number of digraphs and present several results about this digraph invariant, based on which we argue that this concept is a feasible generalization of the (circular) chromatic number of undirected graphs. We also determine the circular chromatic number of arbitrary orientation of any hexagonal chain. It depends on the existence of certain oriented substructure and is always of the form $q=\frac{5k+1}{4k+1}$, where $1\leq k\leq \frac{n}{2}$ is an integer and $n$ is the number of hexagons in the chain.

Title: The linear discrepancy of product of chains

The linear discrepancy $ld(P)$ of a poset $P=(X,\prec)$ is the least integer $m$ for which there exists an injective function $f:X \longrightarrow \{1,2, \ldots ,|X| \}$ such that $f(x) < f(y)$ whenever $x \prec y$ and $|f(x)-f(y)| \le m$ if $x \| y$. The exact value of the linear discrepancy of a product of tw

Title: Foundations of Quasirandomness

Recent work concerning the regularity lemma and its many applications have suggested a new framework for unifying and deepening the areas loosely grouped as "quasirandomness." We discuss this development, its consequences, and problems for future research.

Title: Edge-choosability of planar graphs with no adjacent triangles

We show that if $G$ is a planar graph with no two 3-faces sharing an edge and with $\Delta(G)\neq 5$, then $G$ is $(\Delta(G)+1)$-edge-choosable. This improves results of Wang and Lih and of Zhang and Wu. We also show that if $G$ is a planar graph with $\Delta(G)=5$ and $G$ has no 4-cycles, then $G$ is 6-edge-choosable. In addition, we prove that if $G$ is a planar graph with $\Delta(G)=5$ and the distance between any two 3-faces in $G$ is at least 2, then $G$ is 6-edge-choosable. Finally, we prove that if $G$ is a planar graph with no two 3-faces sharing an edge and with $\Delta(G)\geq 7$, then $G$ has an edge $uv$ with $d(u)+d(v)\leq \Delta(G)+2$. All of our results use the discharging method.

Title: Coverings and packings for radius 1 adaptive block coding

We present an efficient algorithm which recursively constructs an optimal covering containing an optimal packing of the discrete hypercube $Q_{q}$ of dimension $q$ on an finite alphabet of size $t\geq 2$. The packing/covering sets used are adaptive radius 1 hamming balls, which are relaxations of the standard (non-adaptive) radius 1 hamming balls, in either case of size $(t-1)q+1$, and the coverings and packings are of size $\sim t^q/[(t-1)q+1]$. The relaxation corresponds to allowing noiseless, delayless feedback on a noisy communication channel considered by Berlekamp. The non-adaptive versions of these packings and coverings are error-correcting codes with minimum distance 3 and covering codes with covering radius 1, respectively. The construction implicitly provides a winning strategy for the so-called liar game and pathological liar game with 1 lie, previously known for $t=2$ by Pelc, and by Ponomarenko, Yan and the speaker, respectively.

Title: Profile vectors in the poset of subspaces.

The profile vector of a set family $\mathcal{F}$ is $p(\mathcal{F}) \in \mathbf{R}^{n+1}$, where $f_i=|\{F \in \mathcal{F}:|F|=i\}$. The goal of the investigations is to determine the extreme points of the set of profile vectors of a class of families. In the same way for a family $\mathcal{U}$ of subspaces of an $n$-dimensional vectorspace $V$ over $GF(q)$ we define $p(\mathcal{U})=(u_1,\ldots,u_n)$, where $u_i=|\{U \in \mathcal{U}: dim(U)=i\}|$.

A family $\mathcal{U}$ of subspaces is intersecting if all pairs $U,V \in \mathcal{U}$ intersect non-trivially. We determine the extreme points of the profiles of the class of intersecting families.

It is a joint work with Balazs Patkos.

Graph classes characterized both by forbidden subgraphs and degree sequences

Given a set $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$-free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. We say that $\mathcal{F}$ is a degree-sequence-forcing set if, for each graph $G$ in the class $\mathcal{C}$ of $\mathcal{F}$-free graphs, every realization of the degree sequence of $G$ is also in $\mathcal{C}$. We prove that for any $k$ there are finitely many minimal degree-sequence-forcing sets with cardinality $k$. We also give a complete characterization of the degree-sequence-forcing sets $\mathcal{F}$ when $\mathcal{F}$ has cardinality at most two, and partial results when $\mathcal{F}$ has cardinality three.

Title: Distinguishing Chromatic Number of Cartesian Products of Graphs

The distinguishing chromatic number of a graph $G$, $\chi_{_D}(G)$, is the least number of colors needed for a proper coloring of $G$ with the property that the only color-preserving automorphism of $G$ is the identity. That is, we want a proper coloring of a graph that breaks all its symmetries, so that the coloring together with the structure of the graph uniquely determines the vertices. This is an extension of both the chromatic number and the distinguishing number of graphs.

The chromatic number, $\chi(G)$, is an immediate lower bound for $\chi_{_D}(G)$. We show that $\chi_{_D}(G)$ can be surprisingly at most one worse than $\chi(G)$ for $G$ a Cartesian power of any graph. The main theorem is : For every graph $G$, there exists a constant $d_G$ (shown explicitly) such that for all $d\geq d_G$, $\chi_{_D}(G^d) \leq \chi(G) + 1$, where $G^d$ denotes the Cartesian product of $d$ copies of $G$. We also show that for $d \geq 5$, the Cartesian product of $d$ complete graphs (Hamming graphs) has distinguishing chromatic number at most one more the corresponding chromatic number, and we determine the distinguishing chromatic number of hypercubes exactly. This is joint work with J. Choi and S. Hartke.

Title: Excluded submatrices in 0-1 matrices

We say that a 0-1 matrix (or pattern) $P$ is contained in the 0-1 matrix $A$ if it can be obtained from a submatrix of it by changing to $0$ extra $1$ entries. We investigate the extremal function $ex(n,P)}$ which is the maximum number of $1$ entries in an $n$ by $n$ matrix not containing $P$. We present new results related to patterns with linear extremal functions. Further, we give new results related to minimal (for containment) non-linear patterns.

This work is joint with G\'abor Tardos.

Title: Weighted Cross-Intersecting Families

Two set systems $\calA,\,\calB$ are called cross-intersecting if $A\cap B\not=\emptyset$ for all $A\in\calA,\;B\in\calB$. In this talk we investigate weighted cross-intersecting families, that is, if $\alpha,\beta>0$ are given constants, we want to find the maximum of $\alpha|\calA|+\beta|\calB|$ for $\calA,\,\calB$ uniform cross-intersecting families.

As a corollary of the results we will obtain some new bounds on the shadows and the shades of uniform set systems. Finally, we will generalize the LYM inequality not only for cross-intersecting families, but also for arbitrary Sperner families.

Title: Group-Valued Edge Colourings of Cubic Graphs

We study edge-colorings of bridgeless cubic graphs by non-zero elements of finite Abelian groups that satisfy that the colors of the three edges incident with the same vertex are different and their sum is zero. Such a coloring always exists for some groups while for other groups, its existence is equivalent to 3-edge-colorability or is implied by the conjecture of Berge and Fulkerson on the existence of six perfect matchings covering each edge twice. In this talk, we will discuss relaxations of the conjecture of Berge and Fulkerson inspired by this concept.

Joint work with E. Macajova, O. Pangrac, A. Raspaud, J.-S. Sereni, and M. Skoviera)

Title: Between 2- and 3-colorability

The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomial time. To make the complexity gap more precise, we study intermediate graph classes and respective recognition problems. All classes we consider are hereditary in the sense that with every graph G they contain all induced subgraphs of G. According to recent results on the growth of the number of graphs in hereditary classes [J. Balogh, B. Bollobás, D. Weinreich, The speed of hereditary properties of graphs, J. Combin. Theory Ser. B 79 (2000) 131-156], the rates of the growth constitute discrete layers. We conjecture that the complexity jump between 2- and 3-colorability coincides with the combinatorial boundary separating two of the layers. We present some results verifying the conjecture and discuss open problems.

Title: Pattern Avoidance in Ordered Hypergraphs

The so-called F\"{u}redi--Hajnal conjecture, originally posed in 1992 by Zolt\'{a}n F\"{u}redi and P\'{e}ter Hajnal asked what is equivalent to the following question: If $G$ is an ordered bipartite graph with $2n$ vertices and $P$ is an ordered matching on $2k$ vertices, how many edges can $G$ have before it must contain an (ordered) copy of $P$? In 2003, Gabor T\'{a}rdos and I were able to show that the answer grows linearly in $n$. Since then, two different directions of generalizations have been explored. The first, due to J\'{o}zsef Balogh, B\'{e}la Bollob\'{a}s, and Robert Morris, states that {\em any} $n$-vertex ordered hypergraph that avoids a fixed ordered matching can have at most $O(n)$ edges. The second, due to Martin Klazar and myself, states that any $d$-uniform, $d$-partite, $n$-vertex ordered hypergraph that avoids a given $d$-uniform, $d$-partite ordered hyper-matching (each edge contains a unique vertex from each partition) can have at most $O(n^{d-1})$ edges. In this talk, I plan to discuss each of these results (including some interesting implications of the Balogh-Bollob\'{a}s-Morris result) as well as a unified generalization, proved recently by Mitchel Keller and myself, which states that any $n$-vertex, ordered hypergraph that avoids a fixed $d$-uniform, $d$-partite ordered hyper-matching can have at most $O(n^{d-1})$ edges. Since the original F\"{u}redi-Hajnal conjecture has been shown to have powerful implications (most notably, an elegant first solution to the Stanley-Wilf Conjecture, a question concerning permutation enumeration), it is hopeful that this new generalization will have worthwhile implications in the study of more general ordered structures.

Title: Subsums of a finite sum and extreme sets of vertices of the hypercube

We will investigate and show how the following two (and other similar) questions

• How to give a set of $n$ real numbers $x_1, x_2,\ldots, x_n$ none of them being equal to 0, such that they maximize the number of sums $\sum_{i \in B} x_{i}$ equal to 0, where the $B$'s are subsets of $\{1,2,\ldots,n\}$ (or $B$'s are subsets of $\{1,2,\ldots,n\}$ of cardinality $k$ or at most $k$)?
• Let $x_1, x_2,\ldots, x_n$ be given numbers such that $\sum_{i=1}^n x_i > 0$. What is maximum number of negative subsums (or the minimum number of positive subsums) of exactly $k$ of these numbers?

are related to the following ones:

• How many vertices (of a certain property) of the $n$-dimensional cube can be picked such that their span, that is the subspace spanned by them, (or convex or positive span = the cone spanned by them) does not contain or does not intersect certain configurations (elements, hyperplanes)?

Note that since we consider the subspace spanned by the vertices and want to maximize the number of them, it is natural to assume that the vertices form a complete subspace. It turns out, though, that this assumption will not really change the difficulty of the problem.

It will turn out that a special case of Question 1 will yield an unsolved, interesting problem closely related to the Littlewood-Offord and Erd\H os-Moser problems.

Title: Choosability of Graphs with Infinite Sets of Forbidden Differences

The notion of the list-T-coloring is a common generalization of the T-coloring and the list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c such that the color c(v) of each vertex v is contained in its list L(v) and |c(u) - c(v)| is not in T for any two adjacent vertices u and v. The T-choice number of a graph G number is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors.

We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T-choice number of K_2 is finite. For the case when the T-choice number of K_2 is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and one being polynomial in the T-choice number of K_2.

It is easy to see that if T contains an infinite arithmetic progression, the T-choice number of any non-trivial graph is infinite. We show that the converse is false, i.e., we show that there are infinite sets T which contain no arithmetic progression of length greater than two and the T-choice number of K_2 (with respect to such a set T) is infinite.

Title: Biplanar crossing number

The biplanar crossing number $cr_2(G)$ of a graph $G$ is $\min cr(G_1)+cr(G_2)$, where $cr$ is the planar crossing number and $G_1\cup G_2=G$. We show that $cr_2(G)\leq (3/8)cr(G)$. Using this result recursively, we bound the thickness by $\Theta(G)-2\leq K cr_2(G)^{.4057}\log_2 n$ with some constant $K$.

A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph $G$ of this size, which simultaneously has the following properties: $cr(G)$ is roughly as large as it can be for any graph of that size, and $cr_2(G) $ is as small as it can be for any graph of that size. The existence is shown using the probabilistic method.

This is a joint work with \'Eva Czabarka, Ondrej S\'ykora, and Imrich Vr{\v t}o.

Title: The Discrepancy of Quasi-arithmetic Progressions: Power of N or Power of log N?

The 2-colouring discrepancy of arithmetic progressions is a well-known problem in combinatorial discrepancy theory. In 1964, Roth proved that if each integer from 0 to N is coloured red or blue, there is some arithmetic progression in which the number of reds and blues differ by at least (1/20) N^{1/4}. In 1996, Matousek and Spencer showed that this estimate is sharp up to a constant. The parallel question for the discrepancy of homogeneous arithmetic progressions (i.e., the ones containing 0) was raised by Erdos in the 1930s, and it is still not known whether the discrepancy is unbounded. However, it is easy to construct partial colourings with density arbitrarily close to 1 such that all homogeneous arithmetic progressions have bounded discrepancy.

A related problem concerns the discrepancy of quasi-arithmetic progressions. A quasi-arithmetic progression consists of successive multiples of a real number, with each multiple rounded down to the nearest integer. In 1986, Beck showed that given any 2-colouring, the quasi-arithmetic progressions corresponding to almost all real numbers in (1, \infty) have discrepancy at least log* N, the inverse of the tower function. We improve the lower bound to (log N)^{1/4 - \epsilon}, and also show that there is some quasi-arithmetic progression with discrepancy at least (1/50) N^{1/6}. Our results remain valid even if the 2-colouring is replaced by a partial colouring of positive density.

(Dissertation work in progress, supervised by Jozsef Beck.)

Title: Parity Edge-Coloring of Graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. We introduce two parameters. Let $\pecn(G)$ be the least number of colors in an edge-coloring of $G$ having no parity path (a parity edge-coloring). Let $\specn(G)$ be the least number of colors in an edge-coloring of $G$ in which every parity walk is closed (a strong parity edge-coloring). Always $\specn(G)\ge \pecn(G)\ge \chi'(G)$.

The main result is that $\specn(K_n)=2^{\CL{\lg n}}-1$ for all $n$. Furthermore, the optimal coloring for $K_n$ is unique when $n$ is a power of 2 and completely described for all $n$. Also $\pecn(K_n)=\specn(K_n)$ when $n\le16$. The main result strengthens a special case of a result of Daykin and Lov\'asz on Boolean functions.

A connected graph $G$ lies in the hypercube $Q_k$ if and only if $G$ has a parity $k$-edge-coloring in which every cycle is a parity walk. Hence $\pecn(G)\ge\CL{\lg n(G)}$, with equality for paths and even cycles. When $n$ is odd, $\pecn(C_n)=\specn(C_n)=1+\CL{\lg n}$. Also, $\pecn(K_{2,n})=\specn(K_{2,n})$, with value $n$ when $n$ is even and $n+1$ when $n$ is odd. In general, $\specn(K_{m,n})\le m'\CL{n/m'}$, where $m'=2^{\CL{\lg m}}$.

Let $\pecn_r(G)$ be the least number of colors needed to assign $r$ colors to each edge of $G$ so that every choice of a color from the list assigned to each edge yields a parity edge-coloring. Trivially, $\pecn_r(G)\le r\pecn(G)$; we prove that equality holds for paths.

Joint with David P. Bunde, Kevin Milans, and Hehui Wu,University of Illinois - Urbana.