No Arabic abstract
We study hypergraph discrepancy in two closely related random models of hypergraphs on $n$ vertices and $m$ hyperedges. The first model, $mathcal{H}_1$, is when every vertex is present in exactly $t$ randomly chosen hyperedges. The premise of this is closely tied to, and motivated by the Beck-Fiala conjecture. The second, perhaps more natural model, $mathcal{H}_2$, is when the entries of the $m times n$ incidence matrix is sampled in an i.i.d. fashion, each with probability $p$. We prove the following: 1. In $mathcal{H}_1$, when $log^{10}n ll t ll sqrt{n}$, and $m = n$, we show that the discrepancy of the hypergraph is almost surely at most $O(sqrt{t})$. This improves upon a result of Ezra and Lovett for this range of parameters. 2. In $mathcal{H}_2$, when $p= frac{1}{2}$, and $n = Omega(m log m)$, we show that the discrepancy is almost surely at most $1$. This answers an open problem of Hoberg and Rothvoss.
Let $mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m times n$ incidence matrix of $mathcal{H}$ and let us denote $lambda =max_{v perp overline{1},|v| = 1}|Mv|$. We show that the discrepancy of $mathcal{H}$ is $O(sqrt{t} + lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m geq n$ edges is almost surely $O(sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
Given $r$-uniform hypergraphs $G$ and $H$ the Turan number $rm ex(G, H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $rm ex(G, H)$ when $G=G_{n,p}^{(r)}$, the ErdH{o}s-Renyi random $r$-uniform hypergraph, and $H=C_{2ell}^{(r)}$, the $r$-uniform linear cycle of length $2ell$. The case of graphs ($r=2$) is a longstanding open problem that has been investigated by many researchers. We determine $rm ex(G_{n,p}^{(r)}, C_{2ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length decreases as $ell$ grows. Our main technical contribution is a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan. The novelty is that the supersaturation result depends on the codegree of some pairs of vertices in the underlying hypergraph. This approach could be used to prove similar results for other hypergraphs $H$.
We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.
This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
In this expository note we present simple proofs of the lower bound of Ramsey numbers (Erdos theorem), and of the estimation of discrepancy. Neither statements nor proofs require any knowledge beyond high-school curriculum (except a minor detail). Thus they are accessible to non-specialists, in particular, to students. Our exposition is simpler than the standard exposition because no probabilistic language is used. In order to prove the existence of a `good object we prove that the number of `bad objects is smaller than the number of all objects.