More Like this

1. Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

   https://doi.org/10.1017/S0963548320000061  

   Falgas-Ravry, Victor; Markström, Klas; Zhao, Yi (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

   more » « less
2. Assessment for Learning: Helping Children Build on What They Know

   Baroody, A. J.; Pellegrino, J. W. (January 2023, American Educational Research Association Annual Meeting)

   Wiebe, E. N.; Harris, C. J.; Grover, S. (Ed.)

   Efforts to improve instruction frequently focus on fostering meaningful learning—learning based on conceptual understanding—as opposed to knowledge memorized by rote. Consistent with Dewey’s (1963) principle of interaction, fostering meaningful learning entails identifying what children already know and do not know and building on the former to learn (moderately) new knowledge (Claessens & Engel, 2013; Fyfe et al., 2012; Piaget, 1964; Vygotsky, 1978). A learning trajectory (LT) approach to instruction—which includes conceptually and research-based and goals, a research-based learning progression of successive developmental levels, and research-based teaching activities to promote each level—epitomizes such an effort (Clements & Sarama, 2008; Confrey et al., 2012). Formative, classroom-based assessment—ongoing assessment to guide and monitor student learning (Black et al., 2003; Cizek, 2010; Author, 2018a)—is an integral aspect of the LT approach (Daro et al., 2011). In contrast to more commonly used summative assessment strategy (e.g., a unit test given at the end of an instruction unit to assess whether unit content has been mastered and grade progress), formative assessment serves to identify what developmental level a child has already achieved and the next developmentally appropriate level on which instruction should begin (Author, 2018a). Moreover, children are regularly assessed during instruction to gauge whether they–individually or collectively–have mastered a developmental level before instruction proceeds with the next higher level. In sum, “the LT approach involves using formative assessment (National Mathematics Advisory Panel, 2008; Shepard et al., 2018) to provide instructional activities aligned with empirically validated developmental progressions (Fantuzzo, Gadsden, & McDermott, 2011). Although research has shown that LT-based instruction is more efficacious, research is needed to evaluate the add-on value of the formative assessment components of LT-based instruction on student outcomes and the professional development of teachers. This presentation will highlight future lines of research that would provide insight into underlying theory and more productive strategies. Because LTs “need to be supplemented with consideration of obstacles that the student must overcome,” much needs to be learned about the obstacles posed by the content itself, instructional materials, and teachers (Ginsburg, 2009). 

   more » « less
3. A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.72  

   Enoch, Julian; Fox, Kyle; Mesica, Dor; Mozes, Shay (November 2021, 32nd International Symposium on Algorithms and Computation)

   Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.)

   We give an O(k³ Δ n log n min(k, log² n) log²(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of max(k²,k log² n) over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses O(k) invocations of an O(k³ n log³ n)-time algorithm for maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the k-apex graphs that arise in our modification of Wang’s procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan [JACM 1988]. 

   more » « less
4. Faster Algorithms for Rooted Connectivity in Directed Graphs

   Chekuri, Chandra; Quanrud, Kent (July 2021, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021))

   Bansal, Nikhil; Merelli, Emanuela; Worrell, James (Ed.)

   We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the dense-graph high-connectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems. We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)-approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity. Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity. 

   more » « less
5. Definable Regularity Lemmas for NIP Hypergraphs

   https://doi.org/10.1093/qmath/haab011  

   Chernikov, Artem; Starchenko, Sergei (March 2021, The Quarterly Journal of Mathematics)

   null (Ed.)

   Abstract We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov\'asz-Szegedy for graphs of bounded VC-dimension. We also consider the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the corresponding results for graphs in the literature. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples, in particular for graphs definable in the p-adics. 

   more » « less