Filters

36 Hits in 4.5 sec

### Counting Homomorphisms to K4-minor-free Graphs, modulo 2 [chapter]

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný
2021 Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2  ...  We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H.  ...  Furthermore we thank Holger Dell for pointing out the tight conditional lower bound for counting independent sets modulo 2 in  .  ...

### Goursat's theorem and the Zassenhaus lemma

Joachim Lambek
It is now easily shown that if A and B are sets with a limit operation satisfying Kl, K3 and K4, then any one-to-one correspondence between A and B is continuous if it has a closed graph.  ...  (for example, 1, 20) do not count division among the operations; the first to do so was apparently Evans (7) .  ...

### ARITHMETIC OF POTTS MODEL HYPERSURFACES

MATILDE MARCOLLI, JESSICA SU
2013 International Journal of Geometric Methods in Modern Physics (IJGMMP)
We focus on the behavior of the number of points over finite fields for these hypersurfaces, in comparison with the graph hypersurfaces of perturbative quantum field theory defined by the Kirchhoff graph  ...  We consider Potts model hypersurfaces defined by the multivariate Tutte polynomial of graphs (Potts model partition function).  ...  In the case of the Ising model, where q = 2, the counting function N p (Z K4,q=2 ) is the one computed in (5.11).  ...

### Arithmetic of Potts model hypersurfaces [article]

Matilde Marcolli, Jessica Su
2011 arXiv   pre-print
We focus on the behavior of the number of points over finite fields for these hypersurfaces, in comparison with the graph hypersurfaces of perturbative quantum field theory defined by the Kirchhoff graph  ...  We consider Potts model hypersurfaces defined by the multivariate Tutte polynomial of graphs (Potts model partition function).  ...  In the case of the Ising model, where q = 2, the counting function N p (Z K4,q=2 ) is the one computed in (5.11).  ...

### Ideals of Graph Homomorphisms [article]

Alexander Engstrom, Patrik Noren
2011 arXiv   pre-print
Keeping the categorical structure of graphs in mind we give previous results a more functorial context and generalize them by introducing the ideals of graph homomorphisms.  ...  In combinatorial commutative algebra and algebraic statistics many toric ideals are constructed from graphs.  ...  If k ≥ 2 then µ(I C 2k →⫰ ) = k. Proof. Consider the cycle C 2k with vertices 0, 1, . . . 2k − 1 and edges {v, v + 1} counting modulo 2k.  ...

### Homomorphism preservation theorems

Benjamin Rossman
2008 Journal of the ACM
For a finite structure B, let CSP(B) denote the class of finite structures A that have a homomorphism to B.  ...  .: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula of equal quantifier-rank. equivalent in the finite  ...  . , 2 n } and relations E A = {(i, j) : i−j ≡ 1 or −1 modulo 2 n +1} and P A = {0, 2, 4, . . . , 2 n −2, 2 n }.  ...

### Topology of real algebraic curves near the non-singular tropical limit [article]

Cédric Le Texier
2021 arXiv   pre-print
In that case, we count the number of even and odd ovals of those curves in terms of the dual subdivision, and construct some new counter-examples to Ragsdale's conjecture.  ...  Adding the minor M to the minor of D T given by the same rows and columns as M , we obtain the Laplacian mod 2 of the graph K m,n (respectively K l,m,n ) as a minor of Q Γ T , hence K m,n (respectively  ...  to the minor Q are all zero.  ...

### Turán H-densities for 3-graphs [article]

Victor Falgas-Ravry, Emil R. Vaughan
2012 arXiv   pre-print
Given an $r$-graph $H$ on $h$ vertices, and a family $\mathcal{F}$ of forbidden subgraphs, we define $\ex_{H}(n, \mathcal{F})$ to be the maximum number of induced copies of $H$ in an $\mathcal{F}$-free  ...  We also establish that $\pi_{4.2}(\emptyset)=3/4,$ where 4.2 denotes the 3-graph on 4 vertices with exactly 2 edges.  ...  Acknowledgement We would like to thank Colin Reid for coming up with the idea that led to the lower bound construction in Theorem 18.  ...

### How is a graph like a manifold? [article]

Ethan Bolker, Victor Guillemin, Tara Holm
2002 arXiv   pre-print
Another example is the classical parallel redrawing problem, which turns out to be closely related to the problem of computing the second Betti number of a complex compact (^*)^n-manifold.  ...  In this article, we discuss some classical problems in combinatorics which can be solved by exploiting analogues between graph theory and the theory of manifolds.  ...  This shows the connection we defined above on the graph K4. When we think of K 4 just as an abstract 4-regular graph we find that it has 10 different connections (up to graph automorphism).  ...

### Carving-width and contraction trees for tensor networks [article]

J. Jakes-Schauer, D. Anekstein, P. Wocjan
2019 arXiv   pre-print
We study the problem of finding contraction orderings on tensor networks for physical simulations using a syncretic abstract data type, the contraction-tree, and explain its connection to temporal and  ...  We have implemented the Ratcatcher of Seymour and Thomas for determining the carving-width of planar networks, in order to offer experimental evidence that this measure of spatial complexity makes a generally  ...  permission to redistribute Netcon; and Eduardo Mucciolo for sharing the graphics of figs. 6 and 7, as well as the term 'bottleneck.'  ...

### Around generalized external zomotopal algebras of graphs [article]

Boris Shapiro, Ilya Smirnov, Arkady Vaintrob
2022 arXiv   pre-print
Following [NSh] we introduce and study a family of deformations of external zonotopal algebras associated to a given undirected graph with possibly multiple edges, but no loops.  ...  We discuss different properties of the Hilbert series of these algebras and present the results of many calculations carried out in Macaulay 2. Several conjectures are formulated.  ...  For G = K 4 , P A K4 is a weighted projective line (topologically S 2 ).  ...

### On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order

J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, Tobias Friedrich, Nikhil Bansal, Emanuela Merelli, James Worrell
2021
First, we introduce the study of quantum graphs to the study of modular counting homomorphisms.  ...  We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph ̄{H} in any finite field of prime order ℤ_p.  ...  Mod Trees Cactus Square-K4-minor-pK3,3zteu, dominoqfree free free Faben and Jerrum  2Ĝ öbel et al.  2ˆĜ öbel et al.  2ˆF ocke et al.  2ˆˆ(ˆ)Ĝ öbel et al.  ...

### Weak containment of measure preserving group actions [article]

Peter Burton, Alexander S. Kechris
2019 arXiv   pre-print
The case of the shift on [0, 1] Γ can be proved with minor modifications.  ...  The case of s Γ can be proved with minor modifications. Thus among the free actions there is a minimum, s Γ , and a maximum a ∞,Γ , in the sense of weak containment.  ...  To see that (iii) implies (ii), note that if n a n /U is not free and s Γ ⊑ n a n /U, then there is non-free a ∈ A(Γ, X, µ) with s Γ ⊑ a ⊑ n a n /U, contradicting Theorem 3.4.  ...

George M Bergman
{"ft_lang_label":"__label__en","ft_lang_prob":0.8263234,"math_prob":0.9748885,"size":9085,"snap":"2022-27-2022-33","text_gpt3_token_len":2681,"char_repetition_ratio":0.10945931,"word_repetition_ratio":0.12002744,"special_character_ratio":0.27429828,"punctuation_ratio":0.1803985,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.995651,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-12T20:53:21Z\",\"WARC-Record-ID\":\"<urn:uuid:595046f5-4701-497c-891e-ef9e144e45c7>\",\"Content-Length\":\"120632\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4fc05a33-36fc-45b7-b38b-90d750b87007>\",\"WARC-Concurrent-To\":\"<urn:uuid:25eb61d9-8e5c-4ec8-906b-3d7a606dbbe2>\",\"WARC-IP-Address\":\"207.241.225.9\",\"WARC-Target-URI\":\"https://scholar.archive.org/search?q=Counting+Homomorphisms+to+K4-Minor-Free+Graphs%2C+Modulo+2.\",\"WARC-Payload-Digest\":\"sha1:ICFB6SVSICD7PTN7BIA7MR535RJE37RF\",\"WARC-Block-Digest\":\"sha1:4VPIICZ3VSKDXGRZDF4RLYVVNN76ST43\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571758.42_warc_CC-MAIN-20220812200804-20220812230804-00420.warc.gz\"}"}