Turán and Ramsey properties of subcube intersection graphs

DOI10.1017/S0963548312000429MaRDI QIDQ4903262zbMATH OpenFDO

Authors J. Robert Johnson, Klas Markström

Publication date 21 January 2013

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.4283

zbMATH Keywords

Ramsey-type problemTurán-type problemvertex graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Graph representations (geometric and intersection representations, etc.) (05C62) Extremal set theory (05D05)

Abstract: The discrete cube ${0,1}^d$ is a fundamental combinatorial structure. A subcube of ${0,1}^d$ is a subset of $2^k$ of its points formed by fixing $k$ coordinates and allowing the remaining $d-k$ to vary freely. The subcube structure of the discrete cube is surprisingly complicated and there are many open questions relating to it. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no $r+1$ of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no $k$ which have non-empty intersection and no $l$ which are pairwise disjoint? These questions are naturally expressed as Tur'an and Ramsey type questions in intersection graphs of subcubes where the intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. Tur'an and Ramsey type problems are at the heart of extremal combinatorics and so these problems are mathematically natural. However, a second motivation is a connection with some questions in social choice theory arising from a simple model of agreement in a society. Specifically, if we have to make a binary choice on each of $n$ separate issues then it is reasonable to assume that the set of choices which are acceptable to an individual will be represented by a subcube. Consequently, the pattern of intersections within a family of subcubes will have implications for the level of agreement within a society. We pose a number of questions and conjectures relating directly to the Tur'an and Ramsey problems as well as raising some further directions for study of subcube intersection graphs.

Recommendations

• Random subcube intersection graphs. I: Cliques and covering
• Subgraphs of a hypercube containing no small even cycles
• scientific article; zbMATH DE number 1990667
• Vertex Turán problems in the hypercube
• Some Turán type results on the hypercube

Cites work

• A note on Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3443668 (Why is no real title available?)
• Intersection patterns of convex sets
• Intersection properties of boxes. I: An upper-bound theorem
• On a packing and covering problem
• On covering graphs by complete bipartite subgraphs
• On Random Intersection Graphs: The Subgraph Problem
• Supersaturated graphs and hypergraphs
• The early evolution of the \(H\)-free process
• The number of cliques in graphs of given order and size
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The Representation of a Graph by Set Intersections
• Voting in agreeable societies

Cited in

(3)

• Random subcube intersection graphs. I: Cliques and covering
• Biclique covers and partitions
• Turán‐ and Ramsey‐type results for unavoidable subgraphs

This page was built for publication: Turán and Ramsey properties of subcube intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903262)