On the inducibility of cycles Hefetz, Dan; Tyomkyn, Mykhaylo
Journal of combinatorial theory. Series B,
November 2018, 2018-11-00, Letnik:
133
Journal Article
Recenzirano
Odprti dostop
In 1975 Pippenger and Golumbic proved that any graph on n vertices admits at most 2e(n/k)k induced k-cycles. This bound is larger by a multiplicative factor of 2e than the simple lower bound obtained ...by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. In the present paper we establish a better upper bound of (128e/81)⋅(n/k)k. This constitutes the first progress towards proving the aforementioned conjecture since it was posed.
Let K3,33 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 K3,33-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.
In 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
A
T
(
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
A
T
(
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
A
T
(
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
A
T
(
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
)
=
c
h
(
G
)
=
A
T
(
G
)
holds for certain families of graphs
G. Some of these results generalize certain known choosability results.
Weak and strong k-connectivity games Ferber, Asaf; Hefetz, Dan
European journal of combinatorics,
January 2014, 2014-01-00, Letnik:
35
Journal Article
Recenzirano
Odprti dostop
For 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.
On degree anti-Ramsey numbers Gilboa, Shoni; Hefetz, Dan
European journal of combinatorics,
February 2017, 2017-02-00, Letnik:
60
Journal Article
Recenzirano
Odprti dostop
The degree anti-Ramsey number ARd(H) of a graph H is the smallest integer k for which there exists a graph G with maximum degree at most k such that any proper edge colouring of G yields a rainbow ...copy of H. In this paper we prove a general upper bound on degree anti-Ramsey numbers, determine the precise value of the degree anti-Ramsey number of any forest, and prove an upper bound on the degree anti-Ramsey numbers of cycles of any length which is best possible up to a multiplicative factor of 2. Our proofs involve a variety of tools, including a classical result of Bollobás concerning cross intersecting families and a topological version of Hall’s Theorem due to Aharoni, Berger and Meshulam.
Let $G$ be an $n$-vertex oriented graph. Let $t(G)$ (respectively $i(G)$) be the probability that a random set of $3$ vertices of $G$ spans a transitive triangle (respectively an independent set). We ...prove that $t(G) + i(G) \geq \frac{1}{9}-o_n(1)$. Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if $H$ is sufficiently far from that construction, then $t(H) + i(H)$ is significantly larger than $\frac{1}{9}$.
We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.
We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-triangles converge to 1/8. Since the random graph
$\mathcal{G}$
n,1/2 is, in particular, ...3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern 10. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ⩾ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.
On the inducibility of cycles Hefetz, Dan; Tyomkyn, Mykhaylo
Electronic notes in discrete mathematics,
August 2017, 2017-08-00, Letnik:
61
Journal Article
In 1975 Pippenger and Golumbic proved that any graph on n vertices admits at most 2e(n/k)k induced k-cycles. This bound is larger by a multiplicative factor of 2e than the simple lower bound obtained ...by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. In the present paper we establish a better upper bound of (128e/81)⋅(n/k)k. This constitutes the first progress towards proving the aforementioned conjecture since it was posed.
For two graphs G and H, write G⟶rbwH if G has the property that every proper colouring of its edges yields a rainbow copy of H. We study the thresholds for such so-called anti-Ramsey properties in ...randomly perturbed dense graphs, which are unions of the form G∪G(n,p), where G is an n-vertex graph with edge-density at least d>0, and d is independent of n.
In a companion paper, we proved that the threshold for the property G∪G(n,p)⟶rbwKℓ is n−1/m2(Kℓ/2), whenever ℓ≥9. For smaller ℓ, the thresholds behave more erratically, and for 4≤ℓ≤7 they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for large cliques.
In particular, we show that the thresholds for ℓ∈{4,5,7} are n−5/4, n−1, and n−7/15, respectively. For ℓ∈{6,8} we determine the threshold up to a (1+o(1))-factor in the exponent: they are n−(2/3+o(1)) and n−(2/5+o(1)), respectively. For ℓ=3, the threshold is n−2; this follows from a more general result about odd cycles in our companion paper.
PDF
