More Like this

1. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2_29  

   Chudnovsky, Maria and ( February 2021 , MATRIX book series)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c∈N such that for every graph G∈C there is a collection P of partitions (X,Y) of the vertex set of G with |P|≤|V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K∩S=∅, then there is (X,Y)∈P with K⊆X and S⊆Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S,K of graphs and show that for every S∈S and K∈K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less
2. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

   https://doi.org/10.19086/aic.2022.6  

   Chudnovsky, Maria ; Abrishami, Tara ; Hajebi, Sepehr ; Spirkl, Sophie ( September 2022 , Advances in Combinatorics)

   A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-_free_ if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)-free graph $G$ has treewidth at most $c\log (|V(G)|)$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $G$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $k$-Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 

   more » « less
3. Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs

   https://doi.org/10.1002/jgt.22556  

   Chudnovsky, Maria ; Fox, Jacob ; Scott, Alex ; Seymour, Paul ; Spirkl, Sophie ( March 2020 , Journal of Graph Theory)

   A graph is ‐freeif it has no induced subgraph isomorphic to , and |G| denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:

   For every graph , there exists such that in every ‐free graph with |G| there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.

   This is equivalent to:

   The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.

   We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs , and we prove that something like it holds for all graphs . More exactly, say is “almost‐bipartite” if is triangle‐free and can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is:

   The sparse linear conjecture holds for all almost‐bipartite graphs .

   (It remains open when is the triangle .) There is also a stronger theorem:

   For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.

   We also prove some variations on the sparse linear conjecture, such as:

   For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

    

   more » « less
4. Learning and Sampling of Atomic Interventions from Observations

   Bhattacharyya, Arnab ; Gayen, Sutanu ; Kandasamy, Saravanan ; Maran, Ashwin ; Vinodchandran, N. V. ( July 2020 , Proceedings of the 37th International Conference on Machine Learning)

   We study the problem of efficiently estimating the effect of an intervention on a single variable using observational samples. Our goal is to give algorithms with polynomial time and sample complexity in a non-parametric setting. Tian and Pearl (AAAI ’02) have exactly characterized the class of causal graphs for which causal effects of atomic interventions can be identified from observational data. We make their result quantitative. Suppose 𝒫 is a causal model on a set V of n observable variables with respect to a given causal graph G, and let do(x) be an identifiable intervention on a variable X. We show that assuming that G has bounded in-degree and bounded c-components (k) and that the observational distribution satisfies a strong positivity condition: (i) [Evaluation] There is an algorithm that outputs with probability 2/3 an evaluator for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The evaluator can return in O(n) time the probability P^(v) for any assignment v to V. (ii) [Sampling] There is an algorithm that outputs with probability 2/3 a sampler for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The sampler returns an iid sample from P^ with probability 1 in O(n) time. We extend our techniques to estimate P(Y | do(x)) for a subset Y of variables of interest. We also show lower bounds for the sample complexity, demonstrating that our sample complexity has optimal dependence on the parameters n and eps, as well as if k=1 on the strong positivity parameter. 

   more » « less
5. On Weak Flexibility in Planar Graphs

   https://doi.org/10.1007/s00373-022-02564-1  

   Lidický, Bernard ; Masařík, Tomáš ; Murphy, Kyle ; Zerbib, Shira ( December 2022 , Graphs and Combinatorics)

   Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable. 

   more » « less