Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWeak regularity and finitely forcible graph limits
106
0
0.0
(
0
)
Added by
Daniel Kral
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovasz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $varepsilon$-regular partition with the number of parts bounded by a polynomial in $varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $varepsilon$-regular partition of $W$ is at least exponential in $varepsilon^{-2}/2^{5log^*varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
rate research
Read More
The theory of graph limits represents large graphs by analytic objects called graphons. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lovasz and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon. This dismisses any hope for a result showing that finitely forcible graphons possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graphons form a meager set in the space of all graphons. In addition, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems, which conceptually are among the simplest kind within extremal graph theory, may in fact have unique optimal solutions with arbitrarily complex structure.
In this note, we show how to obtain a characteristic power series of graphons -- infinite limits of dense graphs -- as the limit of normalized reciprocal characteristic polynomials. This leads to a new characterization of graph quasi-randomness and another perspective on spectral theory for graphons, a complete description of the function in terms of the spectrum of the graphon as a self-adjoint kernel operator. Interestingly, while we apply a standard regularization to classical determinants, it is unclear how necessary this is.
This book is based on Graph Theory courses taught by P.A. Petrosyan, V.V. Mkrtchyan and R.R. Kamalian at Yerevan State University.
This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
Satisfiability of boolean formulae (SAT) has been a topic of research in logic and computer science for a long time. In this paper we are interested in understanding the structure of satisfiable and unsatisfiable sentences. In previous work we initiated a new approach to SAT by formulating a mapping from propositional logic sentences to graphs, allowing us to find structural obstructions to 2SAT (clauses with exactly 2 literals) in terms of graphs. Here we generalize these ideas to multi-hypergraphs in which the edges can have more than 2 vertices and can have multiplicity. This is needed for understanding the structure of SAT for sentences made of clauses with 3 or more literals (3SAT), which is a building block of NP-completeness theory. We introduce a decision problem that we call GraphSAT, as a first step towards a structural view of SAT. Each propositional logic sentence can be mapped to a multi-hypergraph by associating each variable with a vertex (ignoring the negations) and each clause with a hyperedge. Such a graph then becomes a representative of a collection of possible sentences and we can then formulate the notion of satisfiability of such a graph. With this coarse representation of classes of sentences one can then investigate structural obstructions to SAT. To make the problem tractable, we prove a local graph rewriting theorem which allows us to simplify the neighborhood of a vertex without knowing the rest of the graph. We use this to deduce several reduction rules, allowing us to modify a graph without changing its satisfiability status which can then be used in a program to simplify graphs. We study a subclass of 3SAT by examining sentences living on triangulations of surfaces and show that for any compact surface there exists a triangulation that can support unsatisfiable sentences, giving specific examples of such triangulations for various surfaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
