Piercing independent sets in graphs without large induced matching
0
📈
Sign in to get full access
Introduction
The paper discusses a conjecture related to independent sets in graphs. For a graph G, h(G) denotes the smallest subset of vertices that intersects every maximum independent set of G. The conjecture states that if G does not contain a large induced matching of size t, then h(G) can be bounded by a polynomial function of the clique number ω(G).
The authors prove this conjecture, showing that if G has no induced matching of size t, then h(G) ≤ 10^t * t * ω(G)^(3t-3) * log(ω(G)). Their proof is inspired by recent work.
The conjecture is related to other well-studied conjectures in extremal and structural graph theory, such as the Erdős-Hajnal conjecture. Resolving this conjecture has implications for understanding graphs satisfying certain properties, like being χ-bounded or having polynomial-size homogeneous sets.
The proof
The paper discusses several concepts related to graph theory and set systems. It introduces the transversal number, fractional transversal number, and Vapnik-Chervonenkis (VC) dimension of a set system. These concepts are then applied to analyze the size of the maximum independent set in a graph with no large induced matching.
The transversal number measures the minimum size of a set that intersects every set in the given set system. The fractional transversal number is a relaxed version allowing fractional weights. The VC-dimension captures the maximum cardinality of a set that can be shattered by the set system.
The paper proves that the size of the maximum independent set in a graph G with no induced matching of size t is bounded by a function involving the clique number ω(G) and t. Specifically, it shows that the independence number h(G) is at most 10 * t^t * ω(G)^(3t-3) * log(ω(G)).
This bound is obtained by considering the set system of maximum independent sets of G, analyzing its VC-dimension using Ramsey theory, and then applying a theorem relating the transversal number to the fractional transversal number and VC-dimension.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
📈
0
Piercing independent sets in graphs without large induced matching
Jiangdong Ai, Hong Liu, Zixiang Xu, Qiang Zhou
Given a graph $G$, denote by $h(G)$ the smallest size of a subset of $V(G)$ which intersects every maximum independent set of $G$. We prove that any graph $G$ without induced matching of size $t$ satisfies $h(G)le omega(G)^{3t-3+o(1)}$. This resolves a conjecture of Hajebi, Li and Spirkl (Hitting all maximum stable sets in $P_{5}$-free graphs, JCTB 2024).
Read more4/1/2024
🤔
0
The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
Abhishek Dhawan, Yuzhou Wang
We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed that the maximum independent set has density $left(frac{rlog d}{(r-1)d}right)^{1/(r-1)}$. We show that the class of low-degree polynomial algorithms can find independent sets of density $left(frac{log d}{(r-1)d}right)^{1/(r-1)}$ but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Rahman and Virag, and Wein on graphs, and answers a question of Bal and Bennett. We conjecture that this statistical-computational gap holds for this problem. Additionally, we explore the universality of this gap by examining $r$-partite hypergraphs. A hypergraph $H=(V,E)$ is $r$-partite if there is a partition $V=V_1cupcdotscup V_r$ such that each edge contains exactly one vertex from each set $V_i$. We consider the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random $r$-partite hypergraphs with $n$ vertices in each partition and average degree $d$. We prove that the maximum balanced independent set has density $left(frac{rlog d}{(r-1)d}right)^{1/(r-1)}$ asymptotically. Furthermore, we prove an analogous low-degree computational threshold of $left(frac{log d}{(r-1)d}right)^{1/(r-1)}$. Our results recover and generalize recent work of Perkins and the second author on bipartite graphs. While the graph case has been extensively studied, this work is the first to consider statistical-computational gaps of optimization problems on random hypergraphs. Our results suggest that these gaps persist for larger uniformities as well as across many models. A somewhat surprising aspect of the gap for balanced independent sets is that the algorithm achieving the lower bound is a simple degree-1 polynomial.
Read more7/9/2024
🤿
0
Learning-augmented Maximum Independent Set
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang
We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of $n^{1-delta}$ for any $delta>0$. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability $1/2+varepsilon$. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability $1/2 + varepsilon$. Under this setting, we show an algorithm that obtains an $tilde{O}(sqrt{Delta}/varepsilon)$-approximation in $O(m)$ time where $Delta$ is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability $1/2 + varepsilon$. For this setting, we show an $O(1)$-approximation algorithm using $O(n/varepsilon^2)$ total queries and $tilde{O}(m)$ runtime.
Read more7/17/2024
🔄
0
Hypergraphs of girth 5 and 6 and coding theory
Kathryn Haymaker, Michael Tait, Craig Timmons
In this paper, we study the maximum number of edges in an $N$-vertex $r$-uniform hypergraph with girth $g$ where $g in {5,6 }$. Writing $textrm{ex}_r ( N, mathcal{C}_{<g} )$ for this maximum, it is shown that $textrm{ex}_r ( N , mathcal{C}_{ < 5} ) = Omega_r ( N^{3/2 - o(1)} )$ for $r in {4,5,6 }$. We address an unproved claim from [31] asserting a technique of Ruzsa can be used to show that this lower bound holds for all $r geq 3$. We carefully explain one of the main obstacles that was overlooked at the time the claim from [31] was made, and show that this obstacle can be overcome when $rin {4,5,6}$. We use constructions from coding theory to prove nontrivial lower bounds that hold for all $r geq 3$. Finally, we use a recent result of Conlon, Fox, Sudakov, and Zhao to show that the sphere packing bound from coding theory may be improved when upper bounding the size of linear $q$-ary codes of distance $6$.
Read more4/3/2024