9 citations · 25 across the 11 of their papers we have counts for
17 papers
Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets
Michael Anastos, David Fabian, Alp Müyesser +1
We study multigraphs whose edge-sets are the union of three perfect matchings, , , and . Given such a graph and any with $a_1+a_2+a_3…
New Ramsey Multiplicity Bounds and Search Heuristics
Olaf Parczyk, Sebastian Pokutta, Christoph Spiegel +1
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erdős. Most notably, we improve the upper bounds on…
Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
Penny Haxell, Tibor Szabó
In the max-min allocation problem a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players i…
Oriented cycles in digraphs of large outdegree
Lior Gishboliner, Raphael Steiner, Tibor Szabó
In 1985, Mader conjectured that for every acyclic digraph there exists such that every digraph with minimum out-degree at least contains a subdivision of .…
Dichromatic number and forced subdivisions
Lior Gishboliner, Raphael Steiner, Tibor Szabó
We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph , denote by the smallest…
Ryser's Conjecture for -intersecting hypergraphs
Anurag Bishnoi, Shagnik Das, Patrick Morris +1
A well-known conjecture, often attributed to Ryser, states that the cover number of an -partite -uniform hypergraph is at most times larger than its matching number.…
Majority Colorings of Sparse Digraphs
Michael Anastos, Ander Lamaison, Raphael Steiner +1
A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen an…
Enumerating extensions of mutually orthogonal Latin squares
Simona Boyadzhiyska, Shagnik Das, Tibor Szabó
Two Latin squares are said to be orthogonal if, for every ordered pair of symbols, there are coordinates such that and $L_2(i…
Singer difference sets and the projective norm graph
Tamás Mészáros, Lajos Rónyai, Tibor Szabó
We demonstrate a close connection between the classic planar Singer difference sets and certain norm equation systems arising from projective norm graphs. This, on the one hand lea…
Exploring Projective Norm Graphs
Tomas Bayer, Tamás Mészáros, Lajos Rónyai +1
The projective norm graphs provide tight constructions for the Turán number of complete bipartite graphs with . In this paper we determine thei…
The maximum length of -Bootstrap Percolation
József Balogh, Gal Kronenberg, Alexey Pokrovskiy +1
Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges , and we infect…
On the Odd Cycle Game and Connected Rules
Jan Corsten, Adva Mond, Alexey Pokrovskiy +2
We study the positional game where two players, Maker and Breaker, alternately select respectively and previously unclaimed edges of . Maker wins if she succeeds in cl…
Relative power integral bases in infinite families of quartic extensions of quadratic fields
István Gaál, Tí mea Szabó
We consider infinite parametric families of octic fields, that are quartic extensions of quadratic fields. We describe all relative power integral bases of the octic fields over th…
Calculating power integral bases by using relative power integral bases
István Gaál, László Remete, Tí mea Szabó
Let be number fields. We consider the relation of relative power integral bases of over with absolute power integral bases of over . We show how generat…
Extremal Hypergraphs for Ryser's Conjecture: Home-Base Hypergraphs
Penny Haxell, Lothar Narins, Tibor Szabó
Ryser's Conjecture states that any -partite -uniform hypergraph has a vertex cover of size at most times the size of the largest matching. For , the conjecture…
Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs
Penny Haxell, Lothar Narins, Tibor Szabó
In this paper we consider a natural extremal graph theoretic problem of topological sort, concerning the minimization of the (topological) connectedness of the independence complex…
Conflict-free coloring of graphs
Roman Glebov, Tibor Szabó, Gábor Tardos
We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-fr…