84 research outputs found
Ramsey Properties of Randomly Perturbed Hypergraphs
No full textWe study Ramsey properties of randomly perturbed 3-uniform hypergraphs. For t ≥ 2, write K^(3)_t to denote the 3-uniform expanded clique hypergraph obtained from the complete graph K_t by expanding each of the edges of the latter with a new additional vertex. For an even integer t ≥ 4, let M denote the asymmetric maximal density of the pair (K^(3)_t, K^(3)_{t/2}). We prove that adding a set F of random hyperedges satisfying |F| ≫ n^{3-1/M} to a given n-vertex 3-uniform hypergraph H with non-vanishing edge density asymptotically almost surely results in a perturbed hypergraph enjoying the Ramsey property for K^(3)_t and two colours. We conjecture that this result is asymptotically best possible with respect to the size of F whenever t ≥ 6 is even. The key tools of our proof are a new variant of the hypergraph regularity lemma accompanied with a tuple lemma providing appropriate control over joint link graphs. Our variant combines the so called strong and the weak hypergraph regularity lemmata
Spanning-Tree Games
No full textWe introduce and study a game variant of the classical spanning-tree problem. Our spanning-tree game is played between two players, min and max, who alternate turns in jointly constructing a spanning tree of a given connected weighted graph G. Starting with the empty graph, in each turn a player chooses an edge that does not close a cycle in the forest that has been generated so far and adds it to that forest. The game ends when the chosen edges form a spanning tree in G. The goal of min is to minimize the weight of the resulting spanning tree and the goal of max is to maximize it. A strategy for a player is a function that maps each forest in G to an edge that is not yet in the forest and does not close a cycle.
We show that while in the classical setting a greedy approach is optimal, the game setting is more complicated: greedy strategies, namely ones that choose in each turn the lightest (min) or heaviest (max) legal edge, are not necessarily optimal, and calculating their values is NP-hard. We study the approximation ratio of greedy strategies. We show that while a greedy strategy for min guarantees nothing, the performance of a greedy strategy for max is satisfactory: it guarantees that the weight of the generated spanning tree is at least w(MST(G))/2, where w(MST(G)) is the weight of a maximum spanning tree in G, and its approximation ratio with respect to an optimal strategy for max is 1.5+1/w(MST(G)), assuming weights in [0,1]. We also show that these bounds are tight. Moreover, in a stochastic setting, where weights for the complete graph K_n are chosen at random from [0,1], the expected performance of greedy strategies is asymptotically optimal. Finally, we study some variants of the game and study an extension of our results to games on general matroids
Weak and strong k-connectivity games
No full textAbstractFor a positive integer k, we consider the k-vertex-connectivity game, played on the edge set of Kn, the complete graph on n vertices. We first study the Maker–Breaker version of this game and prove that, for any integer k≥2 and sufficiently large n, Maker has a strategy to win this game within ⌊kn/2⌋+1 moves, which is easily seen to be best possible. This answers a question from Hefetz et al. (2009) [6]. We then consider the strong k-vertex-connectivity game. For every positive integer k and sufficiently large n, we describe an explicit first player’s winning strategy for this game
Semi-random process without replacement
No full textSemi-random processes involve an adaptive decision-maker, whose goal is to
achieve some pre-determined objective in an online randomized environment. We
introduce and study a semi-random multigraph process, which forms a
no-replacement variant of the process that was introduced by Ben-Eliezer,
Hefetz, Kronenberg, Parczyk, Shikhelman and Stojakovi\'c (2020). The process
starts with an empty graph on the vertex set . For every positive integers
and , in the th round of the process, the
decision-maker, called \emph{Builder}, is offered the vertex , where
is a sequence of permutations in , chosen
independently and uniformly at random. Builder then chooses an additional
vertex (according to a strategy of his choice) and connects it by an edge to
.
For several natural graph properties, such as -connectivity, minimum
degree at least , and building a given spanning graph (labeled or
unlabeled), we determine the typical number of rounds Builder needs in order to
construct a graph having the desired property. Along the way we introduce and
analyze an urn model which may also have independent interest
Anti-magic graphs via the combinatorial nullstellensatz
No full textAn antimagic labelling of a graph with m edges and n vertices is a bijection from the set of edges to the integers 1,..., m such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it has an antimagic labelling. In [10], Ringel conjectured that every simple connected graph, other than K2, is antimagic. We prove several special cases and variants of this conjecture. Our main tool is the Combinatorial NullStellenSatz (c.f. [1]).
On two generalizations of the Alon–Tarsi polynomial method
No full textAbstractIn a seminal paper (Alon and Tarsi, 1992 [6]), Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs (and thus, in particular, upper bounds on their chromatic number). The upper bound on the choice number of G obtained via their method, was later coined the Alon–Tarsi number of G and was denoted by AT(G) (see e.g. Jensen and Toft (1995) [20]). They have provided a combinatorial interpretation of this parameter in terms of the eulerian subdigraphs of an appropriate orientation of G. Their characterization can be restated as follows. Let D be an orientation of G. Assign a weight ωD(H) to every subdigraph H of D: if H⊆D is eulerian, then ωD(H)=(−1)e(H), otherwise ωD(H)=0. Alon and Tarsi proved that AT(G)⩽k if and only if there exists an orientation D of G in which the out-degree of every vertex is strictly less than k, and moreover ∑H⊆DωD(H)≠0. Shortly afterwards (Alon, 1993 [3]), for the special case of line graphs of d-regular d-edge-colorable graphs, Alon gave another interpretation of AT(G), this time in terms of the signed d-colorings of the line graph. In this paper we generalize both results. The first characterization is generalized by showing that there is an infinite family of weight functions (which includes the one considered by Alon and Tarsi), each of which can be used to characterize AT(G). The second characterization is generalized to all graphs (in fact the result is even more general—in particular it applies to hypergraphs). We then use the second generalization to prove that χ(G)=ch(G)=AT(G) holds for certain families of graphs G. Some of these results generalize certain known choosability results
Joe Woolfe receiving Scroll of Honor award at Israel Bonds presentation at Olympic Hotel, Seattle, October 22, 1968
No full textLeft to right: Brigadier General Yaacov Hefetz, Joe Woolfe, Washington State Governor Dan Evans.
PH Coll 1091.1
Lagrangians of intersecting families and Turán numbers of hypergraphs
No full textNon UBCUnreviewedAuthor affiliation: University of BirminghamOthe
A hypergraph Turán theorem via lagrangians of intersecting families
No full textLet K33,3 be the 3-graph with 15 vertices {xi, yi: 1 ≤ i ≤ 3} and {zij: 1 ≤ i, j ≤ 3}, and 11 edges {x1, x2, x3}, {y1, y2, y3} and {{xi, yj, zij} : 1 ≤ i, j ≤ 3}. We show that for large n, the unique largest K33,3-free 3-graph on n vertices is a balanced blow-up of the complete 3-graph on 5 vertices. Our proof uses the stability method and a result on lagrangians of intersecting families that has independent interest
- …
