Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Ádám, Zsolt"'
Autor:
Bérczi, Gergely, Wagner, Adam Zsolt
We apply a generative AI pattern-recognition technique called PatternBoost to study bootstrap percolation on hypercubes. With this, we slightly improve the best existing upper bound for the size of percolating subsets of the hypercube.
Externí odkaz:
http://arxiv.org/abs/2411.19734
We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first ``local'' phase, a classical search algorithm is used to produce many desirable constructions
Externí odkaz:
http://arxiv.org/abs/2411.00566
Autor:
Mehrabian, Abbas, Anand, Ankit, Kim, Hyunjik, Sonnerat, Nicolas, Balog, Matej, Comanici, Gheorghe, Berariu, Tudor, Lee, Andrew, Ruoss, Anian, Bulanova, Anna, Toyama, Daniel, Blackwell, Sam, Paredes, Bernardino Romera, Veličković, Petar, Orseau, Laurent, Lee, Joonkyung, Naredla, Anurag Murty, Precup, Doina, Wagner, Adam Zsolt
This work studies a central extremal graph theory problem inspired by a 1975 conjecture of Erd\H{o}s, which aims to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles. We formulate this pro
Externí odkaz:
http://arxiv.org/abs/2311.03583
A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete gr
Externí odkaz:
http://arxiv.org/abs/2303.15476
Autor:
Wagner, Adam Zsolt
We demonstrate how by using a reinforcement learning algorithm, the deep cross-entropy method, one can find explicit constructions and counterexamples to several open conjectures in extremal combinatorics and graph theory. Amongst the conjectures we
Externí odkaz:
http://arxiv.org/abs/2104.14516
A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independe
Externí odkaz:
http://arxiv.org/abs/2104.03260
Publikováno v:
In Journal of Combinatorial Theory, Series B January 2024 164:44-67
One of the most classical results in extremal set theory is Sperner's theorem, which says that the largest antichain in the Boolean lattice $2^{[n]}$ has size $\Theta\big(\frac{2^n}{\sqrt{n}}\big)$. Motivated by an old problem of Erd\H{o}s on the gro
Externí odkaz:
http://arxiv.org/abs/2008.04804
The Boolean lattice $2^{[n]}$ is the family of all subsets of $[n]=\{1,\dots,n\}$ ordered by inclusion, and a chain is a family of pairwise comparable elements of $2^{[n]}$. Let $s=2^{n}/\binom{n}{\lfloor n/2\rfloor}$, which is the average size of a
Externí odkaz:
http://arxiv.org/abs/1911.09533
We show that there exists an absolute constant $C>0$ such that any family $\mathcal{F}\subset \{0,1\}^n$ of size at least $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all ei
Externí odkaz:
http://arxiv.org/abs/1911.00487