ﻻ يوجد ملخص باللغة العربية
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
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 hypergra
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
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). Th