We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of ...map homomorphism that preserves both the combinatorial structure (as a graph homomorphism) and the topological structure of the surface (in particular, orientability and genus). Notions such as the core of a graph and the homomorphism order on cores are then extended to maps. We also develop a purely combinatorial framework for various topological features of a map such as the contractibility of closed walks, which in particular allows us to characterize map cores. We then show that the poset of map cores ordered by the existence of a homomorphism is connected and, in contrast to graph homomorphisms, does not contain any dense interval (so it is not universal for countable posets). Finally, we give examples of a pair of cores with an infinite number of cores between them, an infinite chain of gaps, and arbitrarily large antichains with a common homomorphic image.
Tutte’s dichromate for signed graphs Goodall, Andrew; Litjens, Bart; Regts, Guus ...
Discrete Applied Mathematics,
01/2021, Letnik:
289
Journal Article
Recenzirano
Odprti dostop
We introduce the trivariate Tutte polynomial of a signed graph as an invariant of signed graphs up to vertex switching that contains among its evaluations the number of proper colorings and the ...number of nowhere-zero flows. In this, it parallels the Tutte polynomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. The number of nowhere-zero tensions (for signed graphs they are not simply related to proper colorings as they are for graphs) is given in terms of evaluations of the trivariate Tutte polynomial at two distinct points. Interestingly, the bivariate dichromatic polynomial of a biased graph, shown by Zaslavsky to share many similar properties with the Tutte polynomial of a graph, does not in general yield the number of nowhere-zero flows of a signed graph. Therefore the “dichromate” for signed graphs (our trivariate Tutte polynomial) differs from the dichromatic polynomial (the rank–size generating function).
The trivariate Tutte polynomial of a signed graph can be extended to an invariant of ordered pairs of matroids on a common ground set — for a signed graph, the cycle matroid of its underlying graph and its frame matroid form the relevant pair of matroids. This invariant is the canonically defined Tutte polynomial of matroid pairs on a common ground set in the sense of a recent paper of Krajewski, Moffatt and Tanasa, and was first studied by Welsh and Kayibi as a four-variable linking polynomial of a matroid pair on a common ground set.
A Tutte Polynomial for Maps GOODALL, ANDREW; KRAJEWSKI, THOMAS; REGTS, GUUS ...
Combinatorics, probability & computing,
11/2018, Letnik:
27, Številka:
6
Journal Article
Recenzirano
We follow the example of Tutte in his construction of the dichromate of a graph (i.e. the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial in order to construct ...a new polynomial invariant of maps (graphs embedded in orientable surfaces). We call this the surface Tutte polynomial. The surface Tutte polynomial of a map contains the Las Vergnas polynomial, the Bollobás–Riordan polynomial and the Krushkal polynomial as specializations. By construction, the surface Tutte polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.
We construct a new polynomial invariant of maps (graphs embedded in a closed surface, orientable or non-orientable), which contains as specializations the Krushkal polynomial, the Bollobás—Riordan ...polynomial, the Las Vergnas polynomial, and their extensions to non-orientable surfaces, and hence in particular the Tutte polynomial. Other evaluations include the number of local flows and local tensions taking non-identity values in a given finite group.
We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in ...non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well.
On limits of sparse random graphs Vena, Lluis
Electronic notes in discrete mathematics,
October 2016, 2016-10-00, Letnik:
54
Journal Article
We present a notion of convergence for sequences of finite graphs {Gn} that can be seen as a generalization of the Benjamini-Schramm convergence notion for bounded degree graphs, regarding the ...distribution of r-neighbourhoods of the vertices, and the left-convergence notion for dense graphs, regarding, given any finite graph F, the limit of the probabilities that a random map from V(F) to V(Gn) is a graph homomorphism. Furthermore, this presented convergence notion allows us to define, for each p(n) and with high probability, a limit for a sequence of Erdős-Renyi random graphs with Gn∼G(n,p(n)).
We prove a removal lemma for systems of linear equations over finite fields: let
X
1
, …,
X
m
be subsets of the finite field F
q
and let
A
be a (
k × m
) matrix with coefficients in F
q
; if the ...linear system
Ax
=
b
has
o
(
q
m−k
) solutions with
x
i
∈
X
i
, then we can eliminate all these solutions by deleting
o
(
q
) elements from each
X
i
. This extends a result of Green Geometric and Functional Analysis
15
(2) (2005), 340–376 for a single linear equation in abelian groups to systems of linear equations. In particular, we also obtain an analogous result for systems of equations over integers, a result conjectured by Green. Our proof uses the colored version of the hypergraph Removal Lemma.
The number of homomorphisms from a finite graph F to the complete graph Kn is the evaluation of the chromatic polynomial of F at n. Suitably scaled, this is the Tutte polynomial evaluation T(F;1−n,0) ...and an invariant of the cycle matroid of F. De la Harpe and Jaeger 8 asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from F to a fixed graph G depends only on the cycle matroid of F. They showed that this is true when G has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs).
Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs G for which counting homomorphisms to G yields a matroid invariant. We also extend this result to finite weighted graphs G (where to count homomorphisms from F to G includes such problems as counting nowhere-zero flows of F and evaluating the partition function of an interaction model on F).
Coloring graphs by translates in the circle Candela, Pablo; Catalá, Carlos; Hancock, Robert ...
European journal of combinatorics,
August 2021, 2021-08-00, Letnik:
96
Journal Article
Recenzirano
Odprti dostop
The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which ...originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.
Let G be a finite abelian group with exponent n, and let r be a positive integer. Let A be a k×m matrix with integer entries. We show that if A satisfies some natural conditions and |G| is large ...enough then, for each r-coloring of G∖{0}, there is δ depending only on r,n and m such that the homogeneous linear system Ax=0 has at least δ|G|m−k monochromatic solutions. Density versions of this counting result are also addressed.
PDF
